CF853C.Boredom

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.

伊利亚正坐在大都会机场的候机区，百无聊赖地盯着航班时刻表，上面一遍又一遍地显示他的航班延误了。于是他拿出一张纸，决定解几道题。

首先，伊利亚画出了一个 $ n \times n $ 的网格，并在其中标记了 $ n $ 个格子，使得任意两个被标记的格子既不在同一行，也不在同一列。他将网格中边与网格边平行的矩形称为“优美的”，当且仅当该矩形的四个角中恰好有两个是被标记的格子。这样的优美矩形一共有 $ n \cdot (n - 1) / 2 $ 个。

接着，伊利亚在网格上选定了 $ q $ 个边与网格边平行的查询矩形（这些矩形不一定是优美的），并对每个查询矩形，他希望求出其“优美度”。一个矩形的优美度定义为：与其至少共享一个格子的优美矩形的个数。

现在伊利亚担心自己可能赶不及在登机前解完这个问题。你将获得所有被标记格子的位置信息以及所有查询矩形的信息，请帮助伊利亚计算每个查询矩形的优美度。

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 _p_1, _p_2, ..., p__n, separated by spaces (1 ≤ p__i ≤ n, all p__i are different), they specify grid squares marked by Ilya: in column i he has marked a square at row p__i, 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.

输入的第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 200\,000$，$1 \leq q \leq 200\,000$）——分别表示网格的大小和查询矩形的数量。

第二行包含 $n$ 个整数 $p_1,\,p_2,\,\dots,\,p_n$，以空格分隔（$1 \leq p_i \leq n$，所有 $p_i$ 互不相同），它们指定了 Ilya 标记的网格方格：在第 $i$ 列中，他在第 $p_i$ 行标记了一个方格；行号从 $1$ 到 $n$，由下至上编号；列号从 $1$ 到 $n$，从左至右编号。

接下来的 $q$ 行描述查询矩形。每个矩形由四个整数 $l,\,d,\,r,\,u$ 描述（$1 \leq l \leq r \leq n$，$1 \leq d \leq u \leq n$），其中 $l$ 和 $r$ 分别为矩形最左侧与最右侧的列号，$d$ 和 $u$ 分别为矩形最底部与最顶部的行号。

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

对于每个查询矩形，在单独一行输出其美观度。

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:

第一个样例测试中有一个占据整个网格的优美矩形，因此任意查询的答案均为 1。

在第二个样例测试中，第一个查询矩形与 3 个优美矩形相交，如下图所示：

有 5 个优美矩形与第二个查询矩形相交，如下图所示：