题目描述

给定一个长度为 $n$ 的序列

以及 $q$ 个相互独立的询问。

每个询问给出两个整数 $l,r$。对所有满足

的连续子数组

计算其最小未出现非负整数（MEX），并求这些 MEX 的总和。

一个序列的 MEX 是没有在该序列中出现的最小非负整数。例如：

• 序列 $0,1,4,2$ 的 MEX 为 $3$；
• 序列 $1,2,3,4$ 的 MEX 为 $0$。

输入格式

第一行包含两个整数 $n,q$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行包含两个整数 $l,r$，描述一个询问。

输出格式

按照输入顺序，对每个询问输出一行答案。

数据范围

• $1\le n,q\le 2\times10^5$；
• $0\le a_i\le n$；
• $1\le l\le r\le n$。

子任务

样例

输入：
6 3
0 1 2 0 1 3
1 2
3 5
1 6

输出：
3
7
39

样例说明

对于询问 $[1,2]$：

总和为 $3$。

对于询问 $[3,5]$，所有子数组的 MEX 总和为 $7$。

对于询问 $[1,6]$，全部 $21$ 个连续子数组的 MEX 总和为 $39$。