You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个 $1\sim n$ 的排列 $\pi$，以及 $q$ 个询问，每个询问包含一个整数四元组 $( l, r, x, y )$，表示查询有多少个整数二元组 $( u, v )$ 满足：

• $l\le u\le v\le r$；
• 且对于任意 $\forall u\le i\le v$，有 $x\le\pi_i\le y$。

输入格式

第一行，两个整数 $n$，$q$。

第二行 $n$ 个整数，表示 $\pi$。

以下 $q$ 行，每行一个四元组询问。

输出格式

$q$ 行，每一行表示一个询问的答案。

4 1
1 2 3 4
1 4 2 4

6

提示

子任务 1（$34$ points）：$1\le n, q \le 3\times10^4$。

子任务 2（$66$ points）：$1\le n, q \le 2\times10^5$。