T108000 遥不可及(far)

给定一个长度为$n$ 的序列$\{a_n\}$ (从1 开始标号)。 大多数数据结构题会给你$q$ 次询问$[\ l, r \ ]$，然后询问你一个很奇怪的信息，今天也不例外。 世界上最远的距离，就是你在询问区间里，我在询问区间外。 太远的事情都不要着急想了，这道数据结构题只需要你帮助求出区间内两个相等的数最远的距离。 也就是对于每个询问你要求出$\displaystyle \max_{l \le x,y \le r,a_x=a_y} \mid x-y\mid$。

一行三个整数$n,m,q$。 接下来一行$n$ 个整数$a_1,a_2, \dots ,a_n$ 接下来$Q$ 行，每行两个用空格隔开的正整数$l,r$，表示询问区间。

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

对于$20\%$ 的数据$1 \le n, m, q \le 500$。 对于$40\%$ 的数据，$1 \le n, m, q \le 2000$ 对于$60\%$ 的数据, $1 \le n, m, q \le 6000$ 对于$80\%$ 的数据，$1 \le n, m, q \le 5 \times 10^4$ 对于$100\%$ 的数据, $1 \le n, m, q \le 10^5, 1 \le a_i \le m$