Calculate Beauty Values

Append each closed-interval subarray to the beautiful array in order; duplicate elements produced by overlapping intervals are kept. Positions of the original array never selected by any interval are called unused positions; for each unused value, count the elements of beautiful strictly smaller than it, and finally sum these counts.

输入格式

The first line contains n m; the second line contains n values arr; each of the next m lines contains a 0-based closed interval l r. The original gives no value ranges; this site sets 1≤n,m≤100000, −10⁹≤arr[i]≤10⁹, 0≤l≤r<n.

输出格式

Output a single integer answer.

样例 1

输入：

3 1
3 1 4
1 1

输出：

2

样例 2

输入：

3 2
2 5 1
0 0
0 0

输出：

2

样例 3

输入：

2 1
1 2
0 1

输出：

0

样例说明

Example 1: the concatenation is [1], and the unused 3 and 4 each contribute 1, for a total of 2. Example 2: the concatenation is [2,2], the unused 5 contributes 2 and 1 contributes 0, for a total of 2. Example 3: every position is used, so there is no contribution and the answer is 0.