Problem Statement

There is a marathon with $N$ participants. Each participant wears a bib with a serial number from $1$ to $N$, and the course is a straight line with no branches.
Currently, the person with bib $i$ is at a point at distance $A_i$ from the goal. Answer the $Q$ queries described below.

• Query $q$: A pair of integers $(x_q,y_q)$ is given.
  Output how many people the person with bib $x_q$ needs to overtake in order to catch up with the person with bib $y_q$. However, if the person with bib $x_q$ is already at the same position as the person with bib $y_q$ or closer to the goal, output 0.
  More formally, output the number of $z$ satisfying $A_{y_q} < A_z < A_{x_q}$.

Input

$N \ Q$
$A_1 \ A_2 \ \dots \ A_N$
$x_1 \ y_1$
$\dots$
$x_Q \ y_Q$

• $2 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $1 \leq x_q,y_q \leq N$
• $x_q \neq y_q $
• $(x_q,y_q) \neq (x_r,y_r) \ (q \neq r) $
• All inputs are integers.

Output

Process the $Q$ queries and output the result of each query on $1$ line, separated by newlines.

Sample

4 3
7 20 14 8
2 1
3 1
4 1

2
1
0

8 5
18 14 10 15 11 3 13 2
7 8
2 1
2 8
7 6
3 8

3
0
4
2
1