题目描述

给定一个长度为 $n$ 的数组 $a$。有 $m$ 个询问，每个询问给出两个数 $x_i,y_i$。

对一个位置 $j$，定义：

• $\operatorname{lcnt}(j,x)$：数组 $a$ 的前缀 $1..j$ 中，数 $x$ 出现的次数；
• $\operatorname{rcnt}(j,x)$：数组 $a$ 的后缀 $j..n$ 中，数 $x$ 出现的次数；
• $f(i,x,y)=\operatorname{lcnt}(i-1,x)\cdot \operatorname{rcnt}(i,y)$。

对于每个询问 $(x_i,y_i)$，你需要在所有 $j=2,3,\dots,n$ 中最大化 $f(j,x_i,y_i)$，并输出这个最大值。

输入格式

第一行包含两个整数 $n,m$，表示数组长度和询问数量。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$。

接下来 $m$ 行，每行包含两个整数 $x_i,y_i$，表示一个询问。保证 $x_i$ 和 $y_i$ 都在数组中出现过。

输出格式

输出 $m$ 行，每行一个整数，表示对应询问的答案。

数据范围

$2 \le n \le 100000$，$1 \le m \le 100000$，$1 \le a_i,x_i,y_i \le 10^9$。

样例

样例 1

5 3
1 2 3 2 1
1 2
2 2
1 2

2
1
2

样例 2

5 4
1 1 1 2 2
1 1
1 2
2 2
2 1

2
6
1
0

样例解释

样例 1 中，第一个询问为 $(1,2)$：

• $f(2,1,2)=2$
• $f(3,1,2)=1$
• $f(4,1,2)=1$
• $f(5,1,2)=0$

所以答案为 $2$。

第二个询问为 $(2,2)$：

• $f(2,2,2)=0$
• $f(3,2,2)=1$
• $f(4,2,2)=1$
• $f(5,2,2)=0$

所以答案为 $1$。第三个询问与第一个相同，答案仍为 $2$。

子任务