djb 的玩偶配对

题目描述

djb 从 wjr 家里借了总共 $n$ 个玩偶到家里用来装饰

现在他把 $n$ 个玩偶摆成了一排，第 $i$ 个玩偶属于 $a_i$ 系列

现在 djb 突发奇想，他想知道在一段区间 $[l,r]$ 中，是否存在两个相同系列的玩偶 $x,y$ 使得 $a_x == a_y$ 并且它们之间该系列的玩偶数量不少于 $k$ 个

他认为这样的两个玩偶 $x,y$ 是可以配对的，而它的配对值是它们之间的距离，即 $|y - x| + 1)$

djb 想知道在这段区间中，玩偶的配对值最大可以是多少？

当然这么简单的问题一定是难道不倒你的，所以 djb 一共会提出 $q$ 次询问。

输入格式

第一行三个正整数 $n$，$q$ 和 $k$。

第二行 $n$ 个正整数，其中第 $i$ 个数为 $a_i$，表示第 $i$ 个玩偶的系列编号。

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

输出格式

共 $q$ 行，每行一个整数，表示一次询问的回答。 若无解（没有能够匹配的玩偶），则输出 $-1$。

数据范围

对于 $15\%$ 的数据： $n,q \le 10$。 对于另外 $20\%$ 的数据： $n,q\le 5000$。 对于另外 $25\%$ 的数据：保证 $k=0$。 对于 $100\%$ 的数据：有 $1\le n,q,k\le 100000$，$1\le a_i\le 10^9$。

样例输入

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

样例输出

7
-1