E. Ice Cream Sampling
time limit per test
2.5 с
memory limit per test
128 МБ
input
standard input
output
standard output

Tyger is at an ice cream shop where $$$n$$$ flavors are laid out in a row. Each flavor has a unique integer price from $$$1$$$ to $$$n$$$, inclusive.

Tyger samples the flavors over $$$n$$$ days using the following process:

  • On the first day, Tyger picks any flavor he wants.
  • On each following day, he looks at the untried flavors next to the ones he's already had. From these, he picks the one with the lowest cost.
Cody is curious about Tyger's sampling process and decides to ask $$$q$$$ questions. For each question, Cody names a flavor $$$p$$$ and a day $$$k$$$. He wants to know how many different first-day choices Tyger could make that would lead to him trying flavor $$$p$$$ on exactly day $$$k$$$. Tyger just wants to eat ice cream, so help him answer Cody's questions!
Input

The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n, q \leq 10^5)$$$, representing the number of flavors and the number of questions.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, the costs of the flavors. It is guaranteed that $$$a$$$ is a permutation of length $$$n$$$.

The next $$$q$$$ lines each contain two integers $$$p$$$ and $$$k$$$ $$$(1 \leq p \leq n, 1 \leq k \leq n)$$$, representing Cody's questions.

Output

For each of Cody's questions, output a single integer: the number of possible first-day choices that would result in Tyger trying flavor $$$p$$$ on day $$$k$$$.

Scoring

In tests worth $$$20$$$ points, it is guaranteed that $$$n \leq 1000$$$.

Example
Input
7 3
4 2 6 3 7 1 5
3 1
2 3
5 4
Output
1
1
0
Note

For the first question, Tyger can only start with flavor $$$3$$$ on the first day. For the second question, Tyger can only start with flavor $$$4$$$ on the first day, trying flavor $$$3$$$ on the second day and flavor $$$2$$$ on the third. For the third question, it's impossible no matter which flavor Tyger starts with.

Credit: Mishazher