时间限制： 2s

空间限制： 1024MB

Cuber QQ 现在有一个长度为 $n$ 的序列 $a_1,a_2,\cdots,a_n$，他要求你处理他给出的 $m$ 次询问，每一次询问都给出两个整数 $x$ 和 $y$，要求你找到一个 $i$，将他给出的序列分成两部分 $a_1,a_2,\cdots,a_i$ 和 $a_{i+1},a_{i+2},\cdots,a_n$ 使得在 $a_1,a_2,\cdots,a_i$ 中 $x$ 出现的次数 $\bar{x}$ 和在 $a_{i+1},a_{i+2},\cdots,a_n$ 中 $y$ 出现的次数 $\bar{y}$ 的乘积 $\bar{x}\times \bar{y}$ 最大。

输入格式

第一行包含两个正整数 $n,m$ ($1\leq n,m\leq 10^5$)。

第二行 $n$ 个正整数 $a_1,a_2,\cdots,a_n$ ($1\leq a_i\leq 10^9$)。

接下来 $m$ 行，每行两个数 $x,y$ ($1\leq x,y\leq 10^9$)，表示一次询问。

输出格式

对于每一个询问输出一行，一共 $m$ 行，表示答案。

样例 1

输入

5 2
1 2 3 2 1
1 2
2 2

输出

2
1

样例解释

两个查询的答案分别为：

• 分割序列为 $1$ 和 $2,3,2,1$，则 $\bar{x}=1,\bar{y}=2$；
• 分割序列为 $1,2$ 和 $3,2,1$，则 $\bar{x}=1,\bar{y}=1$。

样例 2

见下发文件 occurrences2.in/out.

数据范围