Alice know how to solve the puzzle called counting game.

You are given an array of integers numbered from to .

You have to perform  queries.

For each query, you are given subsegments. Suppose the left and the right endpoints of the -th segment are and () respectively. You need to calculate the total number of pairs of integers , that .   

输入描述:

The first line contains two integer  (), denoting the length of the array  and the number of queries.

The second line contains  integers  ().

Each of the following blocks of lines contains the description of one query. 
For each query, the first line contains an integer , denotes the number of segments. The following  lines contains two integers  (), representing the  segments in the query.

It guaranteed that , .

输出描述:

For each query, output a number in a line indicating the answer.

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

1
0