伊利亚(Ilya)坐在大都会机场的候机区,厌倦了查看一次又一次显示他的飞机延误的时刻表。于是他拿出一张纸,决定解决一些问题。
首先,Ilya 绘制了一个大小为 n × n 的网格,并在其上标记了 n 个方块,使得没有两个标记的方块共享同一行或同一列。如果网格上的边与网格边平行的矩形恰好有两个角正方形被标记,他称该矩形是美丽的。正好有 n·(n - 1) / 2 个漂亮的矩形。
Ilya 在网格上选择了 q 个查询矩形,其边与网格边平行(不一定是漂亮的),并且对于每个矩形,他想找到其美丽程度。矩形的美度是指与给定矩形至少共享一个正方形的漂亮矩形的数量。
现在Ilya认为他可能没有足够的时间来解决这个问题,直到他的航班起飞。给你标记单元格和查询矩形的描述,帮助Ilya找出每个查询矩形的美观程度。
输入
输入的第一行包含两个整数 n 和 q (2 ≤ n ≤ 200 000, 1 ≤ q ≤ 200 000) - 网格的大小和查询矩形的数量。
第二行包含 n 个整数 p1, p2, ..., pn,用空格分隔(1 ≤ pi ≤ n,所有 pi 都不同),它们指定由 Ilya 标记的网格方块:在第 i 列中,他在 pi 行标记了一个方块,行从 1 到 n 编号,从下到上,列从 1 到 n 编号,从左到右。
以下 q 行描述查询矩形。每个矩形由四个整数描述:l、d、r、u(1 ≤ l ≤ r ≤ n,1 ≤ d ≤ u ≤ n),其中l和r是矩形的最左和最右列,d和u是矩形的最底和最顶行。
输出
对于每个查询矩形,在单独的行上输出其美丽程度。
示例
输入 #1
2 3 1 2 1 1 1 1 1 1 1 2 1 1 2 2
输出 #1
1 1 1
输入 #2
4 2 1 3 2 4 4 1 4 4 1 1 2 3
输出 #2
3 5
注意
第一个样本测试有一个漂亮的矩形占据了整个网格,因此任何查询的答案都是 1。
在第二个示例测试中,第一个查询矩形与3个漂亮的矩形相交,如下图所示:
有5个漂亮的矩形与第二个查询矩形相交,如下图所示: