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