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

There are n skyscrapers in a row. The sun illuminates some of the skyscrapers from the left: a skyscraper is in the sun if it is higher than any skyscraper to the left.

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