**Time limit:**1.00 s**Memory limit:**512 MB

Your task is to process $q$ queries where each query has some range $[a,b]$. If we assume that only the skyscrapers in the range $[a,b]$ exist, how many of them are in the sun?

**Input**

The first input line has two integers $n$ and $q$: the number of skyscrapers and queries. The skyscrapers are numbered $1,2,\dots,n$.

The second line has $n$ integers $h_1, h_2, \dots, h_n$: the heights of the skyscrapers.

Finally, there are $q$ lines, each having two integers $a$ and $b$ ($1 \le a \le b \le n$): the range of the query is $[a,b]$.

**Output**

For each query, print one integer: the number of skyscrapers in the sun.

**Example**

Input:

`5 3`

4 1 2 2 3

1 5

2 5

3 4

Output:

`1`

3

1

**Subtask 1 (16 points)**

- $1 \leq n, q \leq 2000$

- $1 \leq h_{i} \leq 10^9$

**Subtask 2 (35 points)**

- $1 \leq n \leq 10^5$

- $1 \leq q \leq 2 \cdot 10^5$

- $1 \leq h_{i} \leq 100$

**Subtask 3 (49 points)**

- $1 \leq n \leq 10^5$

- $1 \leq q \leq 2 \cdot 10^5$

- $1 \leq h_{i} \leq 10^9$