给定一个长度 $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$。