#2877. 鬼鬼的序列

鬼鬼的序列

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

鬼鬼是一个十四岁的少女,她特别喜欢等差数列。出于对等差数列的喜欢,她想找这种序列:向这个序列a\red{a}中加上 不多于k\red{k}个数,使这个新的数列排序后可以得到一个公差为d\red{d}的等差序列。

鬼鬼给你了一个由n\red{n}个整数组成的数列a\red{a}。你的任务是找到它的最长子串,使它是鬼鬼想找的序列。鬼鬼会十分感 谢你的!

输入格式

第一行输入三个整数 n,k,d\red{n,k,d}。(1<=n<=2e5,0<=k<=2e5,0<=d<=1e9\red{1<=n<=2e5, 0<=k<=2e5, 0<=d<=1e9)}

第二行输入 n\red{n }个整数,表示数列a[]\red{a[]}。(1e9<=a[i]<=1e9\red{-1e9 <=a[i] <=1e9)}

输出格式

输出两个整数 L,R\red{L,R,}描述这个最长子串的左/\red{/}右边界。如果有多个最优答案,输出 L\red{L }值最小的。

样例

输入样例

6 1 2
4 3 2 8 6 2

输出样例

3 5

提示

样例解释

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

少年宫模拟测试2 (S组)

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-10-4 23:30
结束于
2023-10-7 5:30
持续时间
54 小时
主持人
参赛人数
13