#4527. K-D-Sequence

内存限制:256 MiB 时间限制:20 Sec

题目描述

我们称一个数列为一个好的k-d数列,当且仅当我们在其中加上最多k个
数之后,数列排序后为一个公差为d的等差数列。
你手上有一个由n个整数组成的数列a。你的任务是找到它的最长连续子
串,使得满足子串为好的k-d数列。

输入格式

第一行包含三个用空格隔开的整数n,k,d(1<=n<=2*10^5;0<=k<=
2*10^5;0<=d<=10^9)。第二行包含n个空格隔开的整数:a1,a2,...,an(-10^9<=ai<=10^9)表示数列a。

输出格式

输出两个用空格隔开的整数L,r(1<=L<=r<=n),表示数列a_L,a_L+1,...,
ar是好k-d数列的子串中最长的。
如果有多个最优答案,输出那个L值最小的。

样例

样例输入


			
6 1 2
4 3 2 8 6 2

样例输出


			
3 5
//第一个测试样例的答案为包括数字 2,8,6 的子串——在加入数字 4 并且
排序之后,它变成了数列 2,4,6,8——公差为 2 的等差数列。

数据范围与提示