Call an element of an array a peak of if it is larger than all elements before it in . The intimidation value of an array is the number of peaks of .
For example, the intimidation value of is and the intimidation value of is (only is intimidating).
You are given a permutation of and are asked to answer queries. These queries are of the form
l r and you must output the intimidation value of the subarray from to 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.
For all subtasks, .
Subtask 1 [30%]
Subtask 2 [70%]
The first line of the input will have two integers, and .
The second line of the input will have integers: the given permutation of .
The following lines contain two space-separated integers each. These values are and of each query.
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