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\)