题目描述

给定一个长度 $n$ 的序列 $a_1,\dots,a_n$，你需要处理 $m$ 次查询，每次查询给出 $l,r$，对应答案为：

$\sum\limits_{L=l}^r \sum\limits_{R=L}^r \sum\limits_{c=1}^n c\cdot \left[R-L+1<2\sum\limits_{i=L}^R [a_i=c] \right]$。

其中 $[\mathrm{cond}]$ 表示如果括号中的条件表达式为真，则对应 $[\mathrm{cond}]=1$，否则对应 $[\mathrm{cond}]=0$。

输入格式

第一行两个整数 $n,m$；

第二行 $n$ 个整数 $a_1,\dots,a_n$

接下来 $m$ 行，每行两个整数 $l,r$ 表示一次查询。

输出格式

共 $m$ 行，每行一个整数，表示每次询问的答案。

3 2
1 1 2
1 3
2 3

6
3

提示

Idea：zjjcth330，Solution：nzhtl1477&ccz181078，Code：ccz181078，Data：ccz181078

对于 $100\%$ 的数据，满足 $1\le n\le 10^6$，$1\le m\le 10^6$，$1\le a_i\le n$，$1\le l\le r\le n$。