题目描述

时过境迁，为了复仇大业，维兹南又一次来到了这片暮光的森林，他想要招募一批菌菇饲养者。

具体的，现在有一排各种颜色的炸弹蘑菇，颜色用 $0\sim n$ 来表示。

• 定义一个区间 $[l,r]$ 的炸弹蘑菇造成的伤害为：最小的未出现在其中的颜色（即该区间颜色集合的 $\operatorname{mex}$）。
• 定义一个咀嚼蘑菇 $[l,r]$ 造成的伤害为：本质不同的区间 $[l',r']\subseteq [l,r]$ 的炸弹蘑菇造成的伤害（$\operatorname{mex}$）的个数。
• 定义一个菌菇饲养者 $[l,r]$ 的伤害为：所有区间 $[l',r']\subseteq [l,r]$ 的咀嚼蘑菇造成的伤害之和。

他要多次向你询问一个菌菇饲养者 $[l,r]$ 的伤害。

简要题意：求区间所有子区间的「子区间本质不同 $\operatorname{mex}$ 个数」之和。

输入格式

第一行两个数 $n,m$，表示序列长度和询问个数。
第二行 $n$ 个数，表示每个蘑菇的颜色。
接下来 $m$ 行，每行两个数 $l,r$，表示询问的区间。

输出格式

共 $m$ 行，第 $i$ 行为第 $i$ 个询问的答案。

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

146
45
1
22
33
1
5
21
4
6

20 10
3 2 1 0 0 0 4 1 2 3 2 1 1 4 5 5 6 3 2 1
1 20
8 18
3 5
1 9
12 16
8 10
1 11
1 16
20 20
3 17

3
621
66
10
121
15
6
192
399
1
295

样例解释（节选）

对于样例一的倒数第三个询问（原文给出的示意）：

数据范围与提示

• $1\le n,m\le 5\times 10^5$
• 每个蘑菇的颜色 $\in [0,n]$