CF407E.k-d-sequence

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.

我们称一个整数序列为“好的 $k$-$d$ 序列”，当且仅当我们最多向其中添加 $k$ 个数，使得排序后该序列构成一个公差为 $d$ 的等差数列。

你得到了一个由 $n$ 个整数组成的序列 $a$。你的任务是找出其最长的连续子段，使得该子段是一个“好的 $k$-$d$ 序列”。

The first line contains three space-separated integers n, k, d (1 ≤ n ≤ 2·105; 0 ≤ k ≤ 2·105; 0 ≤ d ≤ 109). The second line contains n space-separated integers: _a_1, _a_2, ..., a__n ( - 109 ≤ a__i ≤ 109) — the actual sequence.

第一行包含三个以空格分隔的整数 $n$、$k$、$d$（$1 \leq n \leq 2·10^5$；$0 \leq k \leq 2·10^5$；$0 \leq d \leq 10^9$）。第二行包含 $n$ 个以空格分隔的整数：$a_1,\,a_2,\,...,\,a_n$（$-10^9 \leq a_i \leq 10^9$）—— 实际序列。

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.

输出两个用空格分隔的整数 $l$、$r$（满足 $1 \leq l \leq r \leq n$），表示子序列 $a_l,\, a_{l+1},\, \dots,\, a_r$ 是最长的“好”的 $k$-$d$ 序列。

若存在多个最优解，输出其中 $l$ 值最小的那个。

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.

在第一个测试样例中，答案是包含数字 2、8、6 的子段——在添加数字 4 并排序后，它变为序列 2、4、6、8——这是一个公差为 2 的等差数列。