{"raw_statement":[{"iden":"statement","content":"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.\n\nFirst 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.\n\nIlya 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.\n\nNow 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."},{"iden":"input","content":"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.\n\nThe 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.\n\nThe 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."},{"iden":"output","content":"For each query rectangle output its beauty degree on a separate line."},{"iden":"examples","content":"Input\n\n2 3\n1 2\n1 1 1 1\n1 1 1 2\n1 1 2 2\n\nOutput\n\n1\n1\n1\n\nInput\n\n4 2\n1 3 2 4\n4 1 4 4\n1 1 2 3\n\nOutput\n\n3\n5"},{"iden":"note","content":"The first sample test has one beautiful rectangle that occupies the whole grid, therefore the answer to any query is 1.\n\nIn the second sample test the first query rectangle intersects 3 beautiful rectangles, as shown on the picture below:\n\n![image](https://espresso.codeforces.com/ab1c66ff4bb212f2eaa1df6a3126acc2bc79535c.png) ![image](https://espresso.codeforces.com/e4576fb30a1da895a09193faaf3d92ff2bf16cc9.png) ![image](https://espresso.codeforces.com/3d67c946457a83004c99989b9ccf062d66affd1f.png)\n\nThere are 5 beautiful rectangles that intersect the second query rectangle, as shown on the following picture:\n\n![image](https://espresso.codeforces.com/56bf16b394d5a08e28d2fd8d5ad57392f1cc10e0.png) ![image](https://espresso.codeforces.com/c7d7961cd0d50c64b5a1ec104f16bc95254199a2.png) ![image](https://espresso.codeforces.com/fa6096a3000f51ae6f1d798801441540454f6b9f.png) ![image](https://espresso.codeforces.com/c87e98c04601ad2d95d654f7f31371198d98d1d6.png) ![image](https://espresso.codeforces.com/cab8b66423587e485b08708148a8ce2194ac9558.png)"}],"translated_statement":"[{\"iden\":\"statement\",\"content\":\"Ilya 正坐在莫斯科机场的候机区，厌倦了不断显示他的航班延误的时刻表。于是他拿出一张纸，决定解决一些问题。\\n\\n首先，Ilya 画了一个大小为 $n × n$ 的网格，并在网格上标记了 $n$ 个格子，使得没有任何两个标记的格子位于同一行或同一列。他将网格上边与网格边平行的矩形称为 _美丽矩形_，当且仅当该矩形的四个角中恰好有两个是标记的格子。恰好有 $n·(n - 1) / 2$ 个美丽矩形。\\n\\nIlya 在网格上选择了 $q$ 个边与网格边平行的查询矩形（不一定是美丽矩形），对于每个查询矩形，他希望求出它的 _美丽度_。一个矩形的美丽度定义为：与其至少共享一个格子的美丽矩形的个数。\\n\\n现在 Ilya 认为他可能没有足够的时间在航班起飞前解决这个问题。你将获得标记格子的描述和查询矩形的信息，请帮助 Ilya 求出每个查询矩形的美丽度。\\n\\n输入的第一行包含两个整数 $n$ 和 $q$（$2 ≤ n ≤ 200 000$，$1 ≤ q ≤ 200 000$）——网格的大小和查询矩形的数量。\\n\\n第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$，用空格分隔（$1 ≤ p_i ≤ n$，所有 $p_i$ 互不相同），它们指定了 Ilya 标记的格子：在第 $i$ 列，他在第 $p_i$ 行标记了一个格子；行从 $1$ 到 $n$ 从下到上编号，列从 $1$ 到 $n$ 从左到右编号。\\n\\n接下来的 $q$ 行描述查询矩形。每个矩形由四个整数 $l, d, r, u$ 描述（$1 ≤ l ≤ r ≤ n$，$1 ≤ d ≤ u ≤ n$），其中 $l$ 和 $r$ 是矩形最左和最右的列，$d$ 和 $u$ 是矩形最下和最上的行。\\n\\n对于每个查询矩形，请在单独一行输出其美丽度。\\n\\n第一个样例测试中有一个美丽矩形占据整个网格，因此任何查询的答案都是 1。\\n\\n在第二个样例测试中，第一个查询矩形与 3 个美丽矩形相交，如下图所示：\\n\\n  \\n\\n第二个查询矩形与 5 个美丽矩形相交，如下图所示：\\n\\n    \\n\\n\"},{\"iden\":\"input\",\"content\":\"输入的第一行包含两个整数 $n$ 和 $q$（$2 ≤ n ≤ 200 000$，$1 ≤ q ≤ 200 000$）——网格的大小和查询矩形的数量。第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$，用空格分隔（$1 ≤ p_i ≤ n$，所有 $p_i$ 互不相同），它们指定了 Ilya 标记的格子：在第 $i$ 列，他在第 $p_i$ 行标记了一个格子；行从 $1$ 到 $n$ 从下到上编号，列从 $1$ 到 $n$ 从左到右编号。接下来的 $q$ 行描述查询矩形。每个矩形由四个整数 $l, d, r, u$ 描述（$1 ≤ l ≤ r ≤ n$，$1 ≤ d ≤ u ≤ n$），其中 $l$ 和 $r$ 是矩形最左和最右的列，$d$ 和 $u$ 是矩形最下和最上的行。\"},{\"iden\":\"output\",\"content\":\"对于每个查询矩形，请在单独一行输出其美丽度。\"},{\"iden\":\"examples\",\"content\":\"输入：\\n2 3\\n1 2\\n1 1 1 1\\n1 1 1 2\\n1 1 2 2\\n\\n输出：\\n1\\n1\\n1\\n\\n输入：\\n4 2\\n1 3 2 4\\n4 1 4 4\\n1 1 2 3\\n\\n输出：\\n3\\n5\"},{\"iden\":\"note\",\"content\":\"第一个样例测试中有一个美丽矩形占据整个网格，因此任何查询的答案都是 1。在第二个样例测试中，第一个查询矩形与 3 个美丽矩形相交，如下图所示：  第二个查询矩形与 5 个美丽矩形相交，如下图所示：    \"}]}","sample_group":[],"show_order":[],"formal_statement":"Let $ n $ be the size of the grid, and let $ p = [p_1, p_2, \\dots, p_n] $ be a permutation of $ \\{1, 2, \\dots, n\\} $, where $ p_i $ denotes the row index of the marked square in column $ i $. Thus, the set of marked squares is $ M = \\{ (i, p_i) \\mid 1 \\leq i \\leq n \\} $.\n\nA rectangle is **beautiful** if it has exactly two marked squares as opposite corners. Since no two marked squares share a row or column, every pair of distinct marked squares $ (i, p_i) $ and $ (j, p_j) $ with $ i \\ne j $ defines a unique beautiful rectangle with corners at $ (\\min(i,j), \\min(p_i,p_j)) $ and $ (\\max(i,j), \\max(p_i,p_j)) $. The total number of such rectangles is $ \\binom{n}{2} = \\frac{n(n-1)}{2} $.\n\nFor a query rectangle $ R = [l, r] \\times [d, u] $ (i.e., columns from $ l $ to $ r $, rows from $ d $ to $ u $), its **beauty degree** is the number of beautiful rectangles that **share at least one grid square** with $ R $.\n\nLet $ B $ be the set of all beautiful rectangles. For each beautiful rectangle $ b \\in B $, defined by two marked points $ (i, p_i) $ and $ (j, p_j) $, it corresponds to the axis-aligned rectangle with bottom-left $ (\\min(i,j), \\min(p_i,p_j)) $ and top-right $ (\\max(i,j), \\max(p_i,p_j)) $. This rectangle intersects $ R $ if and only if:\n\n$$\n[\\min(i,j), \\max(i,j)] \\cap [l, r] \\ne \\emptyset \\quad \\text{and} \\quad [\\min(p_i,p_j), \\max(p_i,p_j)] \\cap [d, u] \\ne \\emptyset\n$$\n\nThus, the beauty degree of $ R $ is:\n\n$$\n\\left| \\left\\{ \\{i,j\\} \\subseteq \\{1,\\dots,n\\} \\mid i \\ne j, \\; [\\min(i,j), \\max(i,j)] \\cap [l, r] \\ne \\emptyset, \\; [\\min(p_i,p_j), \\max(p_i,p_j)] \\cap [d, u] \\ne \\emptyset \\right\\} \\right|\n$$\n\nEquivalently, define the set of indices $ I = \\{1, 2, \\dots, n\\} $, and for each pair $ i < j $, let $ b_{ij} $ be the beautiful rectangle defined by $ (i, p_i) $ and $ (j, p_j) $. Then:\n\n$$\n\\text{BeautyDegree}(R) = \\sum_{\\substack{1 \\leq i < j \\leq n \\\\ [\\min(i,j), \\max(i,j)] \\cap [l, r] \\ne \\emptyset \\\\ [\\min(p_i,p_j), \\max(p_i,p_j)] \\cap [d, u] \\ne \\emptyset}} 1\n$$\n\nThis is the final formal statement.","simple_statement":null,"has_page_source":false}