说明

时间限制：1 Sec 内存限制：256 MB 输入文件：big.in 输出文件：big.out

给定长度为 $N$ 的排列 $A=\{a_1,a_2,\dots,a_N\}$（所有数字互不相同，值域 $1\le a_i\le N$）。

共有 $Q$ 次询问，每次询问格式：

$1$ $l$ $r$：输出区间 $[l,r]$ 内高位元素的总个数。

设子数组 $A[l:r]$ 为从下标 $l$ 到 $r$ 的连续元素。

定义高位元素：一段数列里第 $i$ 项，是该数列前 $i$ 项的最大值，则称该项为高位元素。

输入格式

第一行 $N,Q$。

第二行 $N$ 个整数 $a_1\dots a_N$。

接下来 $Q$ 行，每行 $1$ $l$ $r$。

输出格式

每组询问输出一个整数，表示区间内高位元素数量。

样例

样例 1

5 5
5 1 2 4 3
1 1 5
1 1 1
1 2 4
1 2 5
1 3 5

1
1
3
3
2

数据范围

对于 20% 的数据，$N,Q \le 1000$。

对于 100% 的数据，$1\le N,Q\le 10^5$，$A$ 是 $1\sim N$ 的排列，元素互不重复，$1\le l\le r\le N$。