题目描述

長さ $N$ の正整数列 $(A_1,\ A_2,\ \ldots,\ A_N)$ と、この数列に関する $Q$ 個のクエリが与えられます。

$q\ =\ 1,\ 2,\ \ldots,\ Q$ のそれぞれについて、$q$ 番目のクエリでは整数の $2$ つ組 $(l_q,\ r_q)$ が与えられるので、
下記の $2$ つの条件をともに満たす整数の $3$ つ組 $(i,\ j,\ k)$ の個数を出力してください。

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

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$Q$ 行出力せよ。 $q\ =\ 1,\ 2,\ \ldots,\ Q$ について、$q$ 行目には $q$ 番目のクエリに対する答えを出力せよ。

题目大意

给定长度为 $N$ 的数列 $a_1,a_2,\cdots,a_N$。

$q$ 组询问，每组询问给定 $l,r$ 且$1\le l\le r \le n$，问存在多少个三元组 $(i,j,k)$，使得 $l\le i < j<k\le r$ 且 $a_i=a_j=a_k$。

10 4
2 7 1 8 2 8 1 8 2 8
1 10
1 9
2 10
5 5

5
2
4
0

20 10
2 2 2 2 1 1 2 2 1 1 1 2 1 2 1 2 2 1 2 1
12 16
17 18
12 18
4 9
13 13
2 5
6 13
2 14
7 14
8 12

1
0
5
2
0
1
11
55
8
1

提示

制約

• $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$
• 入力はすべて整数

Sample Explanation 1

$1$ 番目のクエリについて、問題文中の $2$ つの条件をともに満たす整数の $3$ つ組 $(i,\ j,\ k)$ は、 $ (1,\ 5,\ 9),\ (4,\ 6,\ 8),\ (4,\ 6,\ 10),\ (4,\ 8,\ 10),\ (6,\ 8,\ 10) $ の $5$ 個です。