There are n buildings in a row numbered 1, 2,\dots, n from left to right. You are standing to the left of the first building. You can see a building if it is taller than any building to its left.

Your task is to process q queries: If only buildings in range [a, b] existed, how many buildings would you see?

Input

The first line has two integers n and q: the number of buildings and queries.

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

Finally, there are q lines describing the queries. Each line has two integers a and b.

Output

For each query, print one integer: the number of visible buildings.

Constraints

• 1 \le n \le 10^5
• 1 \le q \le 2 \cdot 10^5
• 1 \le h_i \le 10^9
• 1 \le a \le b \le n

Example

Input:

5 3
4 1 2 2 3
1 5
2 5
3 4

Output:

1
3
1