三元组索引

题目描述

给定一个长度为 $N$ 的正整数序列 $(A_1, A_2, \ldots, A_N)$，以及关于该序列的 $Q$ 个查询。

对每个 $q = 1, 2, \ldots, Q$，第 $q$ 个查询给出整数对 $(l_q, r_q)$；

求满足以下条件的整数三元组 $(i, j, k)$ 的个数：

$l_q \le i \lt j \lt k \le 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$ 行（$q = 1, 2, \ldots, Q$）输出第 $q$ 个查询的答案。

样例

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

5
2
4
0

对于第一个查询，满足条件的整数三元组有五个： $(1, 5, 9), (4, 6, 8), (4, 6, 10), (4, 8, 10), (6, 8, 10)$。

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 \le N \le 2 \times 10^5$
• $1 \le Q \le 2 \times 10^5$
• $1 \le A_i \le 2 \times 10^5$
• $1 \le l_q \le r_q \le N$
• 输入中的所有值均为整数