本题没有可用的提交语言。

题目背景

我不需要什么夜鹰的青焰或是天蝎的赤焰。

因罪恶感而发出美丽光芒的星星对我来说没有任何用处。

秋夜。不知何处的彼方。沙沙地照射夜晚的阳光……

『一个童话』

没错，这就是一个童话。

我是这样理解的。

秋天的夜晚和夏天的夜晚气氛不同。

台风摧毁夏天，带来了秋天的风。

所以，那个夏夜已经不知消失到哪里去了。

题目描述

给你一个 $1\dots n$ 的排列 $a$，共有 $q$ 次询问，每次询问给你一个区间 $[l,r]$，求满足 $l\le i<j<k\le r$ 且 $a_i<a_j<a_k$ 的三元组 $(i,j,k)$ 数量。

输入格式

本题强制在线。

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

第二行 $n$ 个整数 $a_{1\dots n}$。

接下来 $q$ 行，每行两个整数 $l',r'$ 表示询问。你需要将 $l',r'$ 分别异或上次询问的答案得到真实的 $l,r$。特别地，如果这是第一次询问则 $l=l',r=r'$。

输出格式

$q$ 行，每行一个整数表示答案。

5 7
2 3 4 5 1
3 3
1 3
0 4
6 1
0 4
7 0
1 2

0
1
4
1
4
0
0

12 10
4 1 12 6 2 11 5 3 7 9 8 10
8 11
4 14
15 7
12 13
2 7
10 8
4 10
15 0
7 12
14 11

2
12
14
0
3
0
8
0
12
3

20 20
7 13 5 9 12 15 10 19 3 2 6 17 20 16 4 8 18 1 11 14
9 15
8 7
93 93
3 9
29 25
12 13
7 18
24 13
13 11
0 19
140 141
8 13
3 10
18 14
8 16
30 21
20 25
11 16
13 12
11 16

9
92
0
13
2
0
31
31
1
142
0
7
28
1
27
19
0
1
0
1

提示

Idea：critnos，Solution：critnos，Code：critnos，Data：critnos

所有数据保证 $1\le n,q\le 10^5$，$1\le l\le r\le n$，$a$ 是一个 $1\dots n$ 的排列。