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?

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$ .

• $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$

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