Problem Description

Given a sequence $a_1,\dots,a_n$ of length $n$, you need to process $m$ queries. Each query gives $l, r$, and the answer is:

$\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]$.

Here $[\mathrm{cond}]$ means that if the condition expression inside the brackets is true, then $[\mathrm{cond}]=1$; otherwise, $[\mathrm{cond}]=0$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers $a_1,\dots,a_n$.

The next $m$ lines each contain two integers $l, r$, representing a query.

Output Format

Output $m$ lines. Each line contains one integer, representing the answer to each query.

3 2
1 1 2
1 3
2 3

6
3

Hint

Idea: zjjcth330, Solution: nzhtl1477&ccz181078, Code: ccz181078, Data: ccz181078.

Constraints: For $100\%$ of the testdata, $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$.

Translated by ChatGPT 5