k-d-sequence

题意翻译

找一个最长的子区间使得该子区间加入至多 $k$ 个数以后，排序后是一个公差为 $d$ 的等差数列。 多个解输出 $l$ 最小的。

题目描述

We'll call a sequence of integers a good $ k $ - $ d $ sequence if we can add to it at most $ k $ numbers in such a way that after the sorting the sequence will be an arithmetic progression with difference $ d $ . You got hold of some sequence $ a $ , consisting of $ n $ integers. Your task is to find its longest contiguous subsegment, such that it is a good $ k $ - $ d $ sequence.

输入输出格式

输入格式

The first line contains three space-separated integers $ n,k,d $ ( $ 1<=n<=2·10^{5}; 0<=k<=2·10^{5}; 0<=d<=10^{9} $ ). The second line contains $ n $ space-separated integers: $ a_{1},a_{2},...,a_{n} $ ( $ -10^{9}<=a_{i}<=10^{9} $ ) — the actual sequence.

输出格式

Print two space-separated integers $ l,r $ ( $ 1<=l<=r<=n $ ) show that sequence $ a_{l},a_{l+1},...,a_{r} $ is the longest subsegment that is a good $ k $ - $ d $ sequence. If there are multiple optimal answers, print the one with the minimum value of $ l $ .

输入输出样例

输入样例 #1

6 1 2
4 3 2 8 6 2

输出样例 #1

3 5

说明

In the first test sample the answer is the subsegment consisting of numbers 2, 8, 6 — after adding number 4 and sorting it becomes sequence 2, 4, 6, 8 — the arithmetic progression with difference 2.

题意翻译

找一个最长的子区间使得该子区间加入至多 $k$ 个数以后，排序后是一个公差为 $d$ 的等差数列。 多个解输出 $l$ 最小的。