DMOPC '18 Contest 3 P6 - Bob and Suffering

View as PDF

Points: 30 (partial)
Time limit: 2.5s
Memory limit: 1G

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Bob's teachers have conspired to give Bob a major assessment in each of their classes on the same day! Bob has classes and has estimated how much he will suffer from each assessment. He has recorded these estimates in an array of positive integers . He defines the suffering of a subarray to be the product of the minimum element in this subarray and the total sum of the subarray. Given queries of the form l r, output the greatest suffering of any subarray contained in the subarray from to inclusive where the indices are 1-indexed.

Constraints

There are at most different values of

There are at most different values of

Input Specification

The first line will contain two space-separated integers, and .
The next line will contain space-separated integers, .
The next lines will each contain a query of the form l r.

Output Specification

For each of the queries, output a single integer, the largest suffering of a subarray contained in the queried subarray.

Sample Input 1

6 4
3 5 2 3 5 1
2 2
1 3
1 4
2 6

Sample Output 1

25
25
26
30

Explanation for Sample 1

For the first query, the subarray gives a suffering of .
For the second query, the subarray gives a suffering of .
For the third query, the subarray gives a suffering of .
For the fourth query, the subarray gives a suffering of .

Sample Input 2

5 10
1 2 2 3 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 2

4
8
14
25
8
14
25
10
25
25

Sample Input 3

10 12
8 2 5 4 1 5 9 8 7 3
1 10
2 4
3 7
7 9
4 6
2 3
7 7
5 10
3 3
1 4
6 8
2 8

Sample Output 3

168
36
81
168
25
25
81
168
25
64
136
136