Tzanca Hurricane 先生想要去奥林匹斯山拜访他的女神女友。在规划行程时，他了解到了山上连续 $n$ 天的气温。这些气温值可以看作一个包含 $n$ 个整数的数组 $t$，其中 $t_i$ 表示第 $i$ 天的气温。

由于汽油价格上涨，他非常谨慎地控制他那辆红色法拉利的油耗。特别地，他不想在制冷或供暖上浪费汽油。Hurricane 先生不希望气温过低或过高。他有 $q$ 个他认为舒适的气温范围。

对于 Hurricane 先生给出的每个气温范围 $(x, y)$，他很好奇有多少个不同的数对 $(\ell, r)$ 满足 $\min(t_\ell, t_{\ell+1}, \dots, t_r) = x$ 且 $\max(t_\ell, t_{\ell+1}, \dots, t_r) = y$。请帮他计算出这个结果。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)。

第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$ ($1 \le t_i \le n$)。

接下来的 $q$ 行描述查询。第 $i$ 行包含整数 $x_i$ 和 $y_i$ ($1 \le x_i \le y_i \le n$)。

输出格式

输出包含 $q$ 行，第 $i$ 行包含一个整数，即第 $i$ 个查询的答案。

样例

输入 1

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

输出 1

5
0
4