题目背景

咕咕咕~

题目描述

给定一个长度为 $n$ 的一个 $1$~$n$ 的排列 $A_{1 - n}$。

给定 $q$ 个询问四元组 $( l, r, x, y )$ :

表示询问 有多少个二元组 $( u, v )$ 满足 :

• $[u, v] \neq \varnothing$
• $[u, v] \subset [l, r]$
• $\min\limits_{i \in [u, v]} \{ A_i \} \ge x$
• $\max\limits_{i \in [u, v]} \{ A_i \} \le y$

输入格式

第一行，两个整数 $n$, $q$.

第二行 $n$ 个整数，表示 $A$.

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

输出格式

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

4 1
1 2 3 4
1 4 2 4

6

提示

Subtask1( 34pts ) : $n, q \le 3*10^4$

Subtask2( 66pts ) : $n, q \le 2*10^5$