Pleasure Sum Query

Mivik is writing an article. He has n candidate words, where the i-th word has a length of a_i. He chooses a starting word at position l and writes continuously for q seconds. At the j-th second (for j from 1 to q), he writes the word at position l+j-1 and gains a pleasure value equal to $$ \max_{i=l}^{l+j-1}a_i $$ Your task is to calculate, for each query, the total pleasure value accumulated during the writing session, i.e., $$ \sum_{i=l}^{l+q-1}\max_{j=l}^{i}a_j $$

inputFormat

The input is given via standard input and has the following format:

• The first line contains two integers n and m, where n is the number of words and m is the number of queries.
• The second line contains n integers: a₁, a₂, ..., a_n, representing the lengths of the words.
• Each of the following m lines contains two integers l and q, indicating that Mikiv starts writing at position l and writes for q seconds.

outputFormat

For each query, output a single integer on a new line – the total pleasure value obtained from that writing session.

sample

5 1
1 2 3 2 1
1 3

6