Call an element of an array ~A~ a peak of ~A~ if it is larger than all elements before it in ~A~. The intimidation value of an array is the number of peaks of ~A~.

For example, the intimidation value of ~1, 2, 3, 4, 5~ is ~5~ and the intimidation value of ~5, 4, 3, 2, 1~ is ~1~ (only ~5~ is intimidating).

You are given a permutation of ~1, 2, \dots, N~ and are asked to answer ~Q~ queries. These queries are of the form l r and you must output the intimidation value of the subarray from ~l~ to ~r~ inclusive. Note that an element can be a peak of a subarray, but not a peak of the entire array. However, the intimidation value of the subarray would account for this element, while it would not be counted for the entire array.

Constraints

For all subtasks:

~1 \le l \le r \le N~

Subtask 1 [30%]

~1 \le N \le 2\,000~

~1 \le Q \le 5\,000~

Subtask 2 [70%]

~1 \le N \le 10^6~

~1 \le Q \le 10^6~

Input Specification

The first line of the input will have two integers, ~N~ and ~Q~.

The second line of the input will have ~N~ integers: the given permutation of ~1, 2, \dots, N~.

The following ~Q~ lines contain two space-separated integers each. These values are ~l~ and ~r~ of each query.

Output Specification

For each query, output the answer on a new line.

Sample Input 1

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

Sample Output 1

2
2
1

Sample Input 2

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

Sample Output 2

1
3
1
1