## DMOPC '17 Contest 1 P5 - Intimidating Arrays

View as PDF

Points:15 (partial)
Time limit:2.0s
Memory limit:256M
Author:

Problem type

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.

#### Input Specification

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.

#### 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