You are given a permutation $a$ of $1\dots n$. There are $q$ queries. Each query provides an interval $[l, r]$, and you need to find the number of triples $(i, j, k)$ such that $l \le i < j < k \le r$ and $a_i < a_j < a_k$.

Input

This problem is online.

The first line contains two integers $n$ and $q$.

The second line contains $n$ integers $a_{1\dots n}$.

The next $q$ lines each contain two integers $l', r'$ representing a query. You must XOR $l'$ and $r'$ with the answer to the previous query to obtain the actual $l$ and $r$. Specifically, if this is the first query, $l = l'$ and $r = r'$.

Output

For each query, output one integer on a new line representing the answer.

Examples

Input 1

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

Output 1

0
1
4
1
4
0
0

Input 2

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

Output 2

2
12
14
0
3
0
8
0
12
3

Input 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

Output 3

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

Subtasks

Idea: critnos, Solution: critnos, Code: critnos, Data: critnos

All data guarantees $1 \le n, q \le 10^5$, $1 \le l \le r \le n$, and $a$ is a permutation of $1\dots n$.