U406794 【2023年10月多校联训B层联赛2】 珠子

【2023年10月多校联训B层联赛2】T1 数据点水到爆炸，自造

小 F 有 $n$ 颗珠子排成一个序列，每个珠子有一个颜色，颜色共 $m$ 种，编号为 $1, 2, 3, \cdots,m$。 她想取出一段连续的珠子，对于每一种颜色 $i$，要求取出的珠子的个数在 $[L_i, R_i]$ 之间。 求有多少种取珠子的方案。

第一行两个整数 $m, n$，表示珠子数和颜色数。 第二行 $n$ 个整数 $c_1, c_2, c_3, \cdots, c_n$，表示第 $i$ 个珠子的颜色。 第 $3 \sim m + 2$ 行每行两个整数 $L_i, R_i$，意义见上。

输出一个整数，表示方案数。

对于 $30\%$ 的数据，$n, m \le 200$。 对于 $100\%$ 的数据，满足 $n, m \le 2 \times 10^5$。 保证 $\forall i: 0 \le L_i \le R_i \le, 1 \le c_i \le m$。