같은 수 쌍

길이가 $N$인 수열 $A$가 있다. $Q$개의 쿼리에 대해 구간 안에서 같은 값을 가진 순서쌍의 개수를 출력하라.

각 쿼리마다 $l \leq i < j \leq r$이면서 $A_i=A_j$인 순서쌍 $(i,j)$의 개수를 구해야 한다.

첫 번째 줄에 수열의 길이 $N$과 쿼리의 개수 $Q$가 주어진다. $(1 \leq N,Q \leq 200\,000)$

두 번째 줄에 수열의 원소 $A_1,A_2,\ldots,A_N$이 주어진다. $(-10^9 \leq A_i \leq 10^9)$

세 번째 줄부터 $Q$개의 줄에 걸쳐 두 정수 $l$, $r$이 주어진다. $(1 \leq l \leq r \leq N)$

각 쿼리마다 조건을 만족하는 순서쌍의 개수를 한 줄에 하나씩 출력한다.