## DMOPC '17 Contest 1 P5 - Intimidating Arrays

View as PDFCall 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.

#### Constraints

For all subtasks, .

##### Subtask 1 [30%]

##### Subtask 2 [70%]

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

## Comments