A9422 | $k-d-sequence$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

C++ 编辑器

输入

输出