给定一个长度 $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$ 行，每行一个整数，表示每次询问的答案。
样例数据
样例 1 输入
3 2 1 1 2 1 3 2 3
样例 1 输出
6 3
样例 2 ~ 3
见下发文件
子任务
注意，使用捆绑测试。
对于 $30\%$ 的数据，满足 $1\le n\le 10^3$，$1\le m\le 10^3$，$1\le a_i\le n$，$1\le l\le r\le n$。
对于 $60\%$ 的数据，满足 $1\le n\le 10^5$，$1\le m\le 10^5$，$1\le a_i\le n$，$1\le l\le r\le n$。
对于另外 $20\%$ 的数据，满足 $1 \le a_i \le 2$。
对于 $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$。