Migrated from Lutece 3121 重塑的记忆

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag：单调栈，线段树

“时间飞快的流逝，唯独现在，我有一种想对爱因斯坦发牢骚的心情，冈部，时间根据每个人的主观感受，既会变长，也会变短，相对论真是既浪漫又伤感的东西呢。”

给定长为 $n$ 的序列 $\{a\}$，以及常数 $k$ 和 $d$。求最长的区间，满足将该区间所有元素按升序排序后，插入至多 $k$ 个值，能得到一个公差为 $d$ 的的等差数列。输出区间端点 $l$ 和 $r$。如果有多个长度相同的满足条件的区间，输出使得 $l$ 最小的区间。

Input

第一行，三个正整数 $n,k,d$。 第二行，$n$ 个整数，第 $i$ 个数表示 $a_i$。

Output

一行，两个正整数 $l,r$。

Samples

7 3 2
13 9 14 10 -2 2 4

4 7

Constraints

$1\leq n,k\leq 10^5$，$0\leq d\leq 10^9$，$-10^9\leq a_i\leq 10^9$

Resources

2024 UESTC ICPC Training for Data Structures