Stone的txl数

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

Stone 将一个序列中 m 个区间的和命名为 txl 数(区间重叠部分只取一次)。

现在,Stone 从 QAQ 的桌子上获得了一个序列,他想知道这个序列的 txl 数是多少。

Input

输入数据有多组(数据组数不超过 50),到 EOF 结束。

每组数据第一行为两个数 n, m (1 <= n <= 10^5, 1 <= m <= 1000),分别代表序列的长度和区间的个数。

第二行为 n 个数代表该序列,(1 <= a[i] <= 10^7);接下来 m 行每行两个数 l, r (1 <= l <= r <= n),代表区间 [l, r]。

Output

对于每组数据,输出一行,表示该序列的 txl 数。

Sample Input

10 3
1 2 3 4 5 6 7 8 9 10
1 3
2 4
3 5

Sample Output

15

Hint

Source

【2016级ACM集训队第二次选拔赛】Stone