You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

巡给你序列 $a_1,a_2,\dots,a_n$。定义 $c(l,r)$ 表示 $a_l,a_{l+1},\dots,a_r$ 中出现的数的个数。

八奈见杏菜有 $q$ 个询问，每次给定 $l,r$。输出最大的 $r_0-l_0+1$ 满足：

• $l\leq l_0\leq r_0\leq r$；
• $c(l_0,r_0)\neq c(l,r)$。

如果不存在这样的 $l_0,r_0$，输出 $0$。

输入格式

第一行两个正整数表示 $n,q$。

接下来 $n$ 个正整数表示 $a_1,a_2,\dots,a_n$。

接下来 $q$ 行，每行两个正整数表示 $l,r$。

输出格式

$q$ 行，每行一个非负整数。

样例 $1$

【样例输入】

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

【样例输出】

1
2
3
0

样例 $2$

见附加样例。

数据范围

对所有数据，满足 $1\leq n,q\leq 10^6$，$1\leq a_i\leq n$。

特殊性质：$a_i$ 在 $[1,2]$ 当中随机生成。