lzh 的玩偶配对
说明
lzh 从 wjr 家里借了总共 $n$ 个玩偶到家里用来装饰
现在他把 $n$ 个玩偶摆成了一排，第 $i$ 个玩偶属于 $a_i$ 系列
现在 lzh 突发奇想，他想知道在一段区间 $[l,r]$ 中，是否存在两个相同系列的玩偶 $x,y$ 使得 $a_x == a_y$ 并且它们之间该系列的玩偶数量不少于 $k$ 个
他认为这样的两个玩偶 $x,y$ 是可以配对的，而它的配对值是它们之间的距离，即 $|y - x| + 1)$
lzh 想知道在这段区间中，玩偶的配对值最大可以是多少？
当然这么简单的问题一定是难道不倒你的，所以 lzh 一共会提出 $q$ 次询问。
输入格式
第一行三个正整数 ， 和 。
第二行 个正整数，其中第 个数为 ，表示第 个玩偶的系列编号。
接下来 行，每行两个正整数 ，表示一次询问。
对于 $15\%$ 的数据： $n,q \le 10$。
对于另外 $20\%$ 的数据： $n,q\le 5000$。
对于另外 $25\%$ 的数据：保证 $k=0$。
对于 $100\%$ 的数据：有 $1\le n,q,k\le 100000$，$1\le c_i\le 10^9$。
输出格式
共 行，每行一个整数，表示一次询问的回答。
若无解（没有能够匹配的玩偶），则输出 。
样例
8 2 1
1 2 3 1 2 4 1 2
1 8
2 57
-1
相关
在下列比赛中: