Given a sequence $a_1, \dots, a_n$ of length $n$, you need to process $m$ queries. Each query provides $l$ and $r$, and the corresponding 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]$

Where $[\mathrm{cond}]$ is $1$ if the condition in the brackets is true, and $0$ otherwise.

Input

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

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

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

Output

Output $m$ lines, each containing an integer representing the answer to each query.

Examples

Input 1

3 2
1 1 2
1 3
2 3

Output 1

6
3

Examples 2 ~ 3

See the provided files.

Subtasks

Note: Bundled testing is used.

For $30\%$ of the data, $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$.

For $60\%$ of the data, $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$.

For an additional $20\%$ of the data, $1 \le a_i \le 2$.

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