Description

Xiao L likes to communicate and discuss with wise people, and the wise person often gives Xiao L some thinking problems.

Today the wise person came up with another problem for Xiao L. The wise person first abstracted space-time into a two-dimensional plane, then abstracted an event as a point on this plane, and abstracted an era as a rectangle on this plane.

For convenience, let $(a, b) \leq (c, d)$ denote that two points $(a, b)$ and $(c, d)$ on the plane satisfy $a \leq c$ and $b \leq d$.

More specifically, the wise person is given $n$ events, represented by $n$ distinct points $\{(x_i, y_i)\}^n_{i=1}$ on the plane. The wise person is also given $m$ eras, each represented by a rectangle $(r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2})$ on the plane, where $(r_{i,1}, c_{i,1})$ is the lower-left corner and $(r_{i,2}, c_{i,2})$ is the upper-right corner. It is guaranteed that $(r_{i,1}, c_{i,1}) \leq (r_{i,2}, c_{i,2})$. We say that era $i$ contains event $j$ if and only if $(r_{i,1}, c_{i,1}) \leq (x_j, y_j) \leq (r_{i,2}, c_{i,2})$.

The wise person believes that if two events $i, j$ satisfy $(x_i, y_i) \leq (x_j, y_j)$, then these two events form a regret. For all events contained in an era, the regrets formed by them are called the tears of this era, and the number of regrets is called the size of the tears of this era. Now the wise person wants Xiao L to compute the size of the tears for each era.

Xiao L understands that if he cannot answer this question, he will also become tears of the times. Please help him.

Input Format

Read from standard input.

The first line contains two integers $n, m$, representing the number of events and the number of eras.

The second line contains $n$ integers $p_i$, where the $i$-th number means that event $i$ has coordinates $(i, p_i)$ on the plane. It is guaranteed that $p_i$ is a permutation of $1$ to $n$.

Then follow $m$ lines, each containing four integers $r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2}$, representing the rectangle corresponding to each era.

Output Format

Output to standard output.

Output $m$ lines, each containing one integer. On the $i$-th line, output the size of the tears of the $i$-th era.

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

Explanation for Sample 1

For era $1$, the regret it contains is $(6, 7)$ (that is, the regret formed by events $6$ and $7$, same below).

For era $2$, the regrets it contains are $(5, 6), (6, 7), (5, 7), (5, 8)$.

For era $3$, the regrets it contains are $(5, 6), (5, 8)$.

For era $4$, the regrets it contains are $(5, 6), (6, 7), (5, 7), (5, 8)$.

For era $5$, the regrets it contains are $(5, 6), (6, 7), (5, 7), (5, 8)$.

For era $6$, the regrets it contains are $(5, 6), (6, 7), (5, 7), (5, 8)$.

For eras $7, 8, 9$, none of them contains any regret.

Sample 2

See tears/tears2.in and tears/tears2.ans in the contestant directory.

This sample satisfies Special Constraint A (see test point constraints for details).

Sample 3

See tears/tears3.in and tears/tears3.ans in the contestant directory.

This sample satisfies Special Constraint B (see test point constraints for details).

For all test points: $1 \leq n \leq 10^5$, $1 \leq m \leq 2 \times 10^5$, $1 \leq r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2} \leq n$.

Test Point Constraints

The specific limits for each test point are shown in the table below:

Special Constraint A: For all eras $i$, we have $c_{i,1} = 1$ and $c_{i,2} = n$.

Special Constraint B: For any two different eras, the rectangles they represent are either in a containment relationship (one rectangle is inside the other; boundaries may overlap) or are disjoint (the two rectangles share no common point; boundaries are not allowed to touch).

Special Constraint C: There are at most $50$ pairs of events $(i, j)(1 \leq i < j \leq n)$ that do not satisfy $(i, p_i) \leq (j, p_j)$.

Translated by ChatGPT 5