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 days. Through rigorous calculations, he decided that the maximum amount of Tang he can drink on the -th day is . He also decided that he will drink Tang only for a few consecutive days among these 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 queries. In each query, she will give Shelly a range of days . Shelly needs to find the maximum total amount of Tang he can drink within some consecutive subset of days from the -th to -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 and ends at the day , then must be satisfied and he must drink the same amount of Tang on each day of the days in 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 (the number of days in Shelly's schedule) and (the number of Pe Nie's queries).
In the next line, space-separated integers are given, the -th integer representing the maximum amount of Tang Shelly can eat in the -th day.
In each of the following lines, two space-separated integers and are given, representing the range of days Pe Nie provides in her queries.
Print lines, where the -th line contains a single integer representing the answer to Pe Nie's -th query.
5 4 2 5 2 7 9 1 3 1 2 2 4 2 5
6 5 7 14
In the first query, the amount of Tang Shelly can eat on each of the days from the st to the rd day is . So the total amount of Tang he can in that range is , this is the maximum possible.
In the second query, if Shelly eats amounts of Tang each day, the total he can eat is . But if he eats Tang only on the nd day, the total maximum he can eat is .
In the third query, Shelly can eat amounts of Tang on the th day giving the total maximum amount possible.
In the last query, Shelly can eat amounts of Tang each day from the th to the th day to obtain a maximum total amount of .