25073번 - Tears 다국어

문제

Let $(a,b) \le (c,d)$ denote two points $(a,b),(c,d)$ on the plane satisfies $a \le c,b \le d$. There are $n$ events denoted by $n$ distinct points $\{(x_i,y_i)\}_{i=1}^n$ on the plane. There are $m$ epochs denoted by a rectangle $(r_{i,1},r_{i,2},c_{i,1},c_{i,2})$ where $(r_{i,1},c_{i,1})$ is the bottom-left corner of the rectangle and $(r_{i,2},c_{i,2})$ is the upper-right corner, and it is guaranteed that $(r_{i,1},c_{i,1}) \le (r_{i,2},c_{i,2})$. We say epoch $i$ includes event $j$ if and only if $(r_{i,1},c_{i,1}) \le (x_j,y_j) \le (r_{i,2},c_{i,2})$.

If two events $i,j$ satisfy $(x_i,y_i) \le (x_j,y_j),ドル then the two events constitute an occurrence of sadness. For all events in an epoch, the occurrences of sadness are called the tear of the epoch, and the size of the tear of the epoch is measured by the number of occurrences of sadness. We'd like to compute the size of the tears of the epochs.

입력

The first line contains two integers $n,m$ denoting the number of events and the number of epochs. The second line contains $n$ integers $p_i,ドル and the $i$-th number denotes event $i$ has coordinate $(i,p_i)$ on the plane. It is guaranteed that $p_i$ is a permutation of 1,ドル 2, \dots, n$. In the following $m$ lines, each line contains four integers $r_{i,1},r_{i,2},c_{i,1},c_{i,2}$ denoting the rectangle corresponding to the epoch.

출력

There are $m$ lines and each line contains an integer. The $i$-th line denotes the size of the tear of epoch $i$.

제한

For all test cases, 1ドル \le n \le 10^5,ドル 1ドル \le m \le 2 \times 10^5,ドル 1ドル \le r_{i,1}, r_{i,2}, c_{i,1}, c_{i,2} \le n$.

힌트