T113173 [IV] Rolling Girl

**赛时通知 : 比赛延后 1.5h** **赛时提醒 : 本题的询问部分已变** 「ロンリーガールはいつまでも 届かない夢見て」 「Rolling Girl —— 总是做着不切实际的梦」

不要紧，摔倒了就在地上滚一圈。（此话出自「代号：wave dog」） 滚上一圈后，你在号板上看到了一道题。 号板上写着一个长度为 $N$ 的数列 $num_{1\dots N}$ 和常数 $K$。 竟然还有 $M$ 次询问，每次询问包含一个区间 $l,r$： $$\max\limits_{l \leq i,j \leq r\ ,\ num_i \not = num_j ,\ \text A(num_i)-\text A(num_j) \leq K} \text A(num_i)$$ 其中 $\text A(\text T)$ 为 $\sum\limits^r_{i=l} [num_i=\text T]$。

第一行三个整数 $N,M,K$。 第二行 $N$ 个正整数，代表 $num_{1\dots N}$。 下面 $M$ 行，每行两个正整数 $l,r$。

一共 $M$ 行，每行一个整数代表答案。

对于 $5\%$ 的数据，$N,M \leq 8 , K=1$； 对于 $15\%$ 的数据，$N,M,K,num_i \leq 10^2$。时间限制为 $0.5\text s$ ； 对于其中 $55\%$ ($15\%$~$70\%$) 的数据，分两种情况 : - 对于前 $20\%$ 的数据，$N,M,K \leq 10^4$，保证数据随机。时间限制为 $1\text s$。 - 对于后 $35\%$ 的数据，$N,M \leq 10^5 , K \leq 5$，保证 $num_{1\dots N}$ 随机。 对于 $100\%$ 的数据，$0 < \max num_i,K,N,M \leq 10^5$。时间限制为 $3\text s$。 注意常数问题，欢迎卡常大佬水过去。