#3f3fy1. 序列（seq）

时间限制：3 s       空间限制：1 GiB       标签： 数据结构 线段树 

算法难度等级：0       思维难度等级：0       实现难度等级：0

给定一个长度为 $n$ 的正整数序列 $a$。

对于一个区间 $[l,r]$，定义其权值为最大的 $x$，使得 $x$ 在 $a[l..r]$ 出现且没有在 a[1..l−1] 和 $a[r+1..n]$ 出现。特别地，如果不存在这样的 $x$，定义其权值为 $0$。

$Q$ 次询问，每次给定区间 $[L,R]$，求 $[L,R]$ 的所有子区间的权值之和。

输入格式

第一行两个正整数 $n,Q$。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$。

接下来 $Q$ 行，每行两个正整数 $L,R$。

输出格式

对于每个询问输出一行一个非负整数，表示答案。

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

27
0
0
9
62
0
0
8
0
62

子任务

本题采用子任务捆绑测试。

对于所有数据，保证 $1\leq n,Q\leq 3\times 10^5$，$1\leq a_i\leq n$。

子任务一（$10$ 分）：$n\leq 500$；

子任务二（$30$ 分）：$n\leq 3000$；

子任务三（$30$ 分）：保证数据随机；

子任务四（$30$ 分）：无特殊限制。