[Cnoi2019] 数字游戏

给定一个 $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$。