Queries on Values

Input

The first line contains two integers $n$ and $q$ (1\le n,q\le 3\cdot 10^5) — the number of array elements and the number of queries, respectively.

The second line contains $n$ integers a_1,a_2,\ldots,a_n (1\le a_i\le 10^6).

Each of the next $q$ lines contains two integers $L$ and $R$ (1\le L\le R\le 10^6) — the value bounds for the corresponding query.

Output

For each query, output one integer — the minimum number of operations required so that all elements whose initial values belong to the segment $[L,R]$ become equal to zero, while all other elements do not change.

Print the answers to the queries on separate lines.

Examples

Note

In the first query, we need to make zero all elements whose initial values belong to the range $[3,6]$. These are the elements at positions 2,3,4,5 with values

This can be done in $3$ operations:

1. subtract $2$ from the subarray $[2,3]$;

2. subtract $3$ from the subarray $[2,4]$;

3. subtract $5$ from the subarray $[5,5]$.

Before each operation, all values in the chosen subarray are equal. After these operations, all required elements are equal to zero, while all other elements remain unchanged. Fewer operations are not sufficient, so the answer is $3$.

In the second query, [L,R]=[1,7], so we need to make all elements of the array equal to zero. This can be done in $6$ operations, for example:

1. subtract $2$ from the subarray $[2,3]$;

2. subtract $2$ from the subarray $[6,6]$;

3. subtract $2$ from the subarray $[2,4]$;

4. subtract $4$ from the subarray $[5,6]$;

5. subtract $1$ from the subarray $[2,7]$;

6. subtract $2$ from the subarray $[1,1]$.

Therefore, the answer to the second query is $6$.

In the third query, [L,R]=[4,4]. There is no element with initial value $4$ in the array, so no operations are needed. The answer is $0$.

Scoring

1. Subtask $1$ ($10$ points): L = R for all queries.

2. Subtask $2$ ($20$ points): a_i \le 2 for all 1 \le i \le n.

3. Subtask $3$ ($30$ points): a_i \le a_{i+1} for all 1 \le i < n, n,q \le 1000.

4. Subtask $4$ ($35$ points): n,q \le 1000.

5. Subtask $5$ ($25$ points): R = n for all queries.

6. Subtask $6$ ($60$ points): a_i \le a_{i+1} for all 1 \le i < n.

7. Subtask $7$ ($170$ points): No additional constraints.