Limits 1s, 512 MB

Shell Don (Shelly in short) is a theoretical physicist who is claimed to be highly intelligent with an IQ of 187.

Shelly has decided to drink Tang (a brand of drink mix) regularly. To start out, he made a plan for the next NN days. Through rigorous calculations, he decided that the maximum amount of Tang he can drink on the ii-th day is AiA_i. He also decided that he will drink Tang only for a few consecutive days among these NN days and on each of those days, he will drink the same amount of Tang.

After hearing this, to make fun of Shelly's intelligence, Pe Nie decided to give Shell Don a math problem. Pe Nie will ask Shelly QQ queries. In each query, she will give Shelly a range of days [L,R][L, R]. Shelly needs to find the maximum total amount of Tang he can drink within some consecutive subset of days from the LL-th to RR-th day in his schedule (note that he must drink the same amount of Tang on each day of his chosen subset).

More formally, if Shelly’s chosen consecutive subset of days starts from the day aa and ends at the day bb, then LabRL\leq a\leq b\leq R must be satisfied and he must drink the same amount of Tang on each day of the days in [a,b][a,b] range. What is the maximum total amount of Tang he can consume?

Despite Shelly's phenomenal intelligence in some sectors, he does have trouble showing true intelligence in many other sectors (especially social common sense and math problems like this). So can you help Shelly in solving this problem so that he is not utterly humiliated in front of Pe Nie?


Input starts with two space-separated integers N (1N105)N\space(1\leq N\leq 10^5) (the number of days in Shelly's schedule) and Q (1Q105)Q\space(1\leq Q\leq 10^5) (the number of Pe Nie's queries).

In the next line, NN space-separated integers are given, the ii-th integer Ai (1Ai109)A_i\space(1\leq A_i\leq 10^9) representing the maximum amount of Tang Shelly can eat in the ii-th day.

In each of the following QQ lines, two space-separated integers LL and R (1LRN)R\space(1\leq L\leq R\leq N) are given, representing the range of days Pe Nie provides in her queries.


Print QQ lines, where the ii-th line contains a single integer representing the answer to Pe Nie's ii-th query.


5 4
2 5 2 7 9
1 3
1 2
2 4
2 5

In the first query, the amount of Tang Shelly can eat on each of the days from the 11st to the 33rd day is 22. So the total amount of Tang he can in that range is 66, this is the maximum possible.

In the second query, if Shelly eats 22 amounts of Tang each day, the total he can eat is 44. But if he eats Tang only on the 22nd day, the total maximum he can eat is 55.

In the third query, Shelly can eat 77 amounts of Tang on the 44th day giving the total maximum amount possible.

In the last query, Shelly can eat 77 amounts of Tang each day from the 44th to the 55th day to obtain a maximum total amount of 1414.


Login to submit.


67% Solution Ratio
tasmeemrezaEarliest, Jan '23
ChatGPTFastest, 0.3s
ChatGPTLightest, 48 MB
ChatGPTShortest, 5340B
Toph uses cookies. By continuing you agree to our Cookie Policy.