Find Sum of Beauties

Each closed interval is taken from the original array and the pieces are concatenated; repeated and overlapping intervals contribute their elements again. An original index covered by any interval has beauty 0; an uncovered index has beauty equal to the number of elements in the concatenated array strictly less than its value. Find the total beauty. The source example miscounted repeated elements; this site corrects it to 12.

输入格式

The first line contains n m, the second line the array, followed by m lines of 0-indexed closed intervals l r. The source had no numeric bounds; this site uses 1≤n,m≤200000, −10^9≤element≤10^9, 0≤l≤r<n.

输出格式

Output a single integer, the answer.

样例 1

输入：

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

输出：

12

样例 2

输入：

2 1
2 2
0 0

输出：

0

样例 3

输入：

3 2
1 3 5
0 0
0 0

输出：

4

样例说明

In the first example the uncovered 3 has 5 smaller elements and the 5 has 7, for a total of 12; the other two examples give 0 and 4.