Description

Satou and Shio give you a 2D plane. For two points $(x_1,y_1),(x_2,y_2)$ on the plane, we say they form a dominance pair (denoted as $(x_1,y_1)\le (x_2,y_2)$) if and only if $x_1\le x_2,\;y_1\le y_2$.

Initially, there are $n$ distinct points $\{(x_i,y_i)\}_{i=1}^n$ on the plane.

You need to answer $m$ queries. Each query gives two points $(x,y),(x',y')$ and asks how many ordered pairs $(i,j)$ satisfy $(x,y)\le (x_i,y_i)\le (x_j,y_j)\le (x',y')$ and $i \neq j$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers. The $i$-th integer $p_i$ indicates that the $i$-th initially given point on the plane is $(i,p_i)$. It is guaranteed that $p_i$ is a permutation of $1$ to $n$.

Then there are $m$ lines. Each line contains four integers separated by spaces, $x,x',y,y'$, representing one query. It is guaranteed that $(x,y)\le (x',y')$.

Output Format

Output $m$ lines. The $i$-th line contains one integer, the answer to the $i$-th query.

9 9
9 8 7 6 2 4 5 3 1
4 9 3 6
2 9 1 8
3 8 2 4
3 9 2 7
2 8 1 6
1 9 1 9
1 3 5 7
2 3 3 3
6 6 6 6

1
4
2
4
4
4
0
0
0

Hint

Idea: ccz181078 & nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: nzhtl1477 & ccz181078.

For $100\%$ of the data, $1 \le n \le 10^5$, $1 \le m \le 2 \times 10^5$.

Sample Explanation

For the first query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(4,6),(6,4),(7,5),(8,3)$. The dominance pair is $(6,4),(7,5)$, and the corresponding ordered pair is $(6,7)$.

For the second query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(2,8),(3,7),(4,6),(5,2),(6,4),(7,5),(8,3),(9,1)$. The dominance pairs are $(5,2),(6,4)$, $(6,4),(7,5)$, $(5,2),(7,5)$, and $(5,2),(8,3)$, and the corresponding ordered pairs are $(5,6),(6,7),(5,7),(5,8)$.

For the third query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(5,2),(6,4),(8,3)$. The dominance pairs are $(5,2),(6,4)$ and $(5,2),(8,3)$, and the corresponding ordered pairs are $(5,6),(5,8)$.

For the fourth query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(4,6),(5,2),(6,4),(7,5),(8,3)$. The dominance pairs are $(5,2),(6,4)$, $(6,4),(7,5)$, $(5,2),(7,5)$, and $(5,2),(8,3)$, and the corresponding ordered pairs are $(5,6),(6,7),(5,7),(5,8)$.

For the fifth query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(4,6),(5,2),(6,4),(7,5),(8,3)$. The dominance pairs are $(5,2),(6,4)$, $(6,4),(7,5)$, $(5,2),(7,5)$, and $(5,2),(8,3)$, and the corresponding ordered pairs are $(5,6),(6,7),(5,7),(5,8)$.

For the sixth query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(1,9),(2,8),(3,7),(4,6),(5,2),(6,4),(7,5),(8,3),(9,1)$. The dominance pairs are $(5,2),(6,4)$, $(6,4),(7,5)$, $(5,2),(7,5)$, and $(5,2),(8,3)$, and the corresponding ordered pairs are $(5,6),(6,7),(5,7),(5,8)$.

For the seventh query, the points $(x_i,y_i)$ that satisfy $(x,y)\le (x_i,y_i)\le (x',y')$ are $(3,7)$, and there are no dominance pairs.

For the eighth query, there are no points $(x_i,y_i)$ satisfying $(x,y)\le (x_i,y_i)\le (x',y')$, and there are no dominance pairs.

For the ninth query, there are no points $(x_i,y_i)$ satisfying $(x,y)\le (x_i,y_i)\le (x',y')$, and there are no dominance pairs.

Input Format

Output Format

Hint

Translated by ChatGPT 5