You are given an array $A$ having $N$ integers. You have to answer $Q$ queries. The $i^{th}$ query is denoted by two integers $L_i, R_i$. The answer to the $i^{th}$ query is $A_{L_i} + \min(A_{L_i},A_{L_i + 1}) + \dots + \min(A_{L_i},A_{L_i + 1} \dots, A_{R_i})$.

For each query find the answer.

Note: Since the size of the input and output is large, please use in memory stack size accordingly otherwise you may see error.

Input format

• The first line of input contains two integers $N, Q$ denoting the length of the array $A$ and the number of queries respectively.
• The second line contains $N$ integers $A_1, A_2,\dots, A_N$ denoting elements of the array $A$.
• Each of the next $Q$ contains two space-separated integers $L_i, R_i$.

Output format

For each query, print the answer in a separate line.

Constraints

$1 \leq N, Q \leq 3\cdot 10^5\\ 1\le A_i\le 10^9\\ 1 \le L_i \le R_i \le N$