题目描述

小 F 有 $n$ 颗珠子排成一个序列，每个珠子有一个颜色，颜色共有 $m$ 种，编号为 $1,2,\ldots ,m$ 。

她想取出一段连续的珠子，对于每一种颜色 $i$ ，要求取出的珠子个数在 $[l_i,r_i]$ ($0\leq l_i\leq r_i\leq n$) 之间。

求有多少种取珠子的方案。

输入格式

第一行两个整数 $n,m$ ，表示珠子数和颜色数。

第二行 $n$ 个整数 $c_1,c_2,\ldots ,c_n$ ($1\leq c_i\leq m$) ，表示 $n$ 个珠子的颜色。

接下来的 $m$ 行每行两个整数 $l_i,r_i$ ，意义如题目中所示。

输出格式

输出一行一个整数表示符合要求的取珠子方案数。

样例

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

4

数据范围与约定

对于 $30\%$ 的数据，$n, m\leq 200$ 。

对于 $60\%$ 的数据， $n,m\leq 2000$ 。

对于 $100\%$ 的数据， $n,m\leq 2\times 10^5$ 。