← 返回题目列表

Codeforces · 407/E

E. k-d 序列

中文机器翻译题面 查看原题

如果我们可以将最多 k 个数字相加,使得排序后的序列将是差值为 d 的算术级数,那么我们将称一个整数序列为良好的 k-d 序列。

你得到了一些序列 a,由 n 个整数组成。你的任务是找到它的最长连续子段,这样它就是一个好的 k-d 序列。

输入

第一行包含三个空格分隔的整数 n、k、d (1 ≤ n ≤ 2·105;0 ≤ k ≤ 2·105;0 ≤ d ≤ 109)。第二行包含 n 个以空格分隔的整数:a1, a2, ..., an ( - 109 ≤ ai ≤ 109) - 实际序列。

输出

打印两个空格分隔的整数 l, r (1 ≤ l ≤ r ≤ n) 表明序列 al, al + 1, ..., ar 是最长的子段,是良好的 k-d 序列。

如果有多个最佳答案,则打印 l 最小值的答案。

示例

输入 #1

6 1 2
4 3 2 8 6 2

输出 #1

3 5

注意

在第一个测试样本中,答案是由数字 2、8、6 组成的子段——加上数字 4 并排序后,它变成序列 2、4、6、8——差值为 2 的算术级数。