Boredom
Contest: Codeforces Round 433 (Div. 1, based on Olympiad of Metropolises)
Difficulty rating: 2100
Tags: data structures

Ilya is sitting in a waiting area of Metropolis airport and is bored of looking at time table that shows again and again that his plane is delayed. So he took out a sheet of paper and decided to solve some problems.

First Ilya has drawn a grid of size n × n and marked n squares on it, such that no two marked squares share the same row or the same column. He calls a rectangle on a grid with sides parallel to grid sides beautiful if exactly two of its corner squares are marked. There are exactly n·(n - 1) / 2 beautiful rectangles.

Ilya has chosen q query rectangles on a grid with sides parallel to grid sides (not necessarily beautiful ones), and for each of those rectangles he wants to find its beauty degree. Beauty degree of a rectangle is the number of beautiful rectangles that share at least one square with the given one.

Now Ilya thinks that he might not have enough time to solve the problem till the departure of his flight. You are given the description of marked cells and the query rectangles, help Ilya find the beauty degree of each of the query rectangles.

Input format:
The first line of input contains two integers n and q (2 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) — the size of the grid and the number of query rectangles.

The second line contains n integers p1, p2, ..., pn, separated by spaces (1 ≤ pi ≤ n, all pi are different), they specify grid squares marked by Ilya: in column i he has marked a square at row pi, rows are numbered from 1 to n, bottom to top, columns are numbered from 1 to n, left to right.

The following q lines describe query rectangles. Each rectangle is described by four integers: l, d, r, u (1 ≤ l ≤ r ≤ n, 1 ≤ d ≤ u ≤ n), here l and r are the leftmost and the rightmost columns of the rectangle, d and u the bottommost and the topmost rows of the rectangle.

Output format:
For each query rectangle output its beauty degree on a separate line.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
The first sample test has one beautiful rectangle that occupies the whole grid, therefore the answer to any query is 1.

In the second sample test the first query rectangle intersects 3 beautiful rectangles, as shown on the picture below:

There are 5 beautiful rectangles that intersect the second query rectangle, as shown on the following picture:

Example input:
2 3
1 2
1 1 1 1
1 1 1 2
1 1 2 2

Example output:
1
1
1

Example input:
4 2
1 3 2 4
4 1 4 4
1 1 2 3

Example output:
3
5

Editorial:
We can't iterate over all interesting rectangles. Let's count number of rectangles that are not intersecting our rectangle. To do it let's calculate number of rectangles to the left, right, up and down of rectangle in query. It can be easily done in O(1) time: suppose we have rectangle with corners (i;pi) and (j;pj). We have min(i, j) - 1 points to the left of rectangle, n - max(i, j) to the right, min(pi, pj) - 1 to the down, etc. If we have x points in some area, there are $$\frac{x(x-1)}{2}$$ rectangles in that area. But now we calculated twice rectangles that are simultaneously to the left and up of our rectangle, left and down, etc. To find number of such rectangles we can iterate over all points and find points which are in these areas and find number of rectangles in area using formula $$\frac{x(x-1)}{2}$$. The complexity is O(q·n).
To solve the problem we need to find number of points in some areas faster. It's quite easy to notice that we just have many queries of finding number of points in some subrectangle. It's classical problem that can be solved with some 2d tree in O(q·log2) solution. But it can be too slow and can not fit into time limit in case of inaccurate implementation. However, you can notice that all queries are offline and find number of points in subrectangle in O(q·logn) time. It's fast enough to pass all tests.