给一个长为 $n$ 的序列 $a$，下标为 $1$ 到 $n$，有 $m$ 次查询操作，每次给出一个区间 $[l,r]$，求一个子区间 $[l',r']$，满足 $l\le l'\le r'\le r$，$[l',r']$ 中出现过的值个数比 $[l,r]$ 中出现过的值个数少，且其长度即 $r'-l'+1$ 最大。若不存在这样的子区间，则输出 $0$。

输入格式

第一行两个数表示 $n,m$。

之后一行 $n$ 个数依次表示序列 $a$ 中的元素。

之后 $m$ 行，每行两个数 $l,r$ 表示一次查询，只需输出该子区间的长度，即 $r'-l'+1$。

输出格式

对于每次查询，输出一行一个数表示答案。

样例数据

样例 1 输入

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

样例 1 输出

1
2
3
0

子任务

Idea：ccz181078，Solution：ccz181078，Code：ccz181078，Data：ccz181078

对于 $20\%$ 的数据，满足 $n,m\le100$。

对于 $40\%$ 的数据，满足 $n,m\le1000$。

对于另外 $20\%$ 的数据，满足 $a_i\le 10$。

对于 $100\%$ 的数据，满足 $1\le n,m,a_i\le 2\times 10^6$。