I. Mountain Climbing Hard
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Goma has been enjoying mountain climbing so much lately that they want to take Peach with them! There is a path of length $$$N$$$ with varying altitudes, and Peach wants to know how many distinct points they can see from certain spots on the path. However, fog is forecasted for the day of their trip, so Peach wants to take that into account when calculating the visible points. Specifically, if a point $$$p$$$ has altitude $$$a_p$$$ and the fog has altitude $$$f$$$, then Peach can see all points $$$q$$$ such that:

  1. The altitude $$$a_q$$$ is strictly less than $$$a_p$$$
  2. There are no points between $$$p$$$ and $$$q$$$ with altitude $$$a_p$$$ or greater
  3. Either $$$a_q \lt a_p \lt f$$$ or $$$f \leq a_q \lt a_p$$$ (points at or above the fog cannot see points strictly below it)

Note that Peach can always see the spot they are currently on.

Input

The first line contains two integers $$$N$$$ $$$(1 \leq N \leq 10^6)$$$ and $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$, where $$$N$$$ is the length of the mountain path and $$$Q$$$ is the number of queries Peach would like to make.

The next line contains $$$N$$$ space separated integers $$$a_1, a_2,\ldots, a_N$$$ where $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$ is the altitude of point $$$i$$$ on the path.

The last $$$Q$$$ lines each contain two integers $$$p$$$ $$$(1 \leq p \leq N)$$$ and $$$f$$$ $$$(1 \leq f \leq 10^9)$$$ which represents a request Peach has to find the number of spots on the mountain visible from point $$$p$$$ given there is fog at altitude $$$f$$$.

Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.

Testcases $$$1-5$$$ the fog is negligible (has an altitude of $$$1$$$).

Testcases $$$6-20$$$ have no additional constraints.

Output

$$$Q$$$ lines with a single integer where the $$$i$$$'th line contains the answer to Peach's $$$i$$$'th query.

Example
Input
10 3
1 2 3 2 4 4 2 4 5 3
2 3
3 2
5 2
Output
2
3
4
Note

The answer to Peach's second query is $$$3$$$ as they can see points $$$2$$$ through $$$4$$$. Note that they cannot see point $$$1$$$ because of the fog at altitude $$$2$$$.

 —

Idea: Bossologist

Preparation: Bossologist

Occurrences: Advanced 5