Problem Statement

You are given a length-$N$ sequence $(A_1, A_2, \ldots, A_N)$ of positive integers, and $Q$ queries about the sequence.

For each $q = 1, 2, \ldots, Q$, the $q$-th query gives you an integer pair $(l_q, r_q)$; print the number of integer triplets $(i, j, k)$ such that

• $l_q \leq i \lt j \lt k \leq r_q$, and
• $A_i = A_j = A_k$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq A_i \leq 2 \times 10^5$
• $1 \leq l_q \leq r_q \leq N$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

N Q
A_1 A_2 \ldots A_N
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

Output

Print $Q$ lines. For $q = 1, 2, \ldots, Q$, the $q$-th line should contain the answer to the $q$-th query.