题目描述
给定一个长度为 $n$ 的序列 $a$ 和两个参数 $m$、$k$。
现在另有一个长度为 $n$ 的序列 $b$。最开始 $b$ 中的每一个元素均为 $0$。
称如下为一个 $x$ 操作（$x\ge 0$）：
- 选定一个整数 $i$，满足 $1\le i\le n$。
- 对于 $\forall i\le j\le \min\left\{i+x,n\right\}$，给 $b_j$ 加上 $(x-(j-i))^k$。
找到并输出最小的 $x$ 使得至少存在一种情况满足：
- 对 $b$ 做 $m$ 次 $x$ 操作后，$\forall 1\le i\le n,b_i\ge a_i$。
若不存在任何一个满足要求的 $x$，输出 -1。
输入格式
第一行三个整数，表示 $n$，$m$ 和 $k$。
第二行 $n$ 个整数，第 $i$ 个表示 $a_i$。
输出格式
一行共一个整数，表示满足要求的最小的 $x$。
样例输入 #1
5 3 0
1 1 2 3 1 2样例输出 #1
3样例解释 #1
一个合法的选择是 $i=1,3,3$。
第一次 $3$ 操作后，$b=[1,1,1,1,1,1]$；
第二次 $3$ 操作后，$b=[1,1,2,2,2,2]$；
第三次 $3$ 操作后，$b=[1,1,3,3,3,3]$。
容易证明不存在一个合法选择使得 $x\lt 3$。
样例输入 #2
5 2 1
13 21 17 16 13样例输出 #2
12样例解释 #2
一个合法的选择是 $i=1,1$。
第一次 $12$ 操作后，$b=[12,11,10,9,8]$；
第二次 $12$ 操作后，$b=[24,22,20,18,16]$。
容易证明不存在一个合法选择使得 $x\lt 12$。
样例输入 #3
5 2 2
13 21 17 16 13样例输出 #3
6样例解释 #3
一个合法的选择是 $i=1,3$。
第一次 $6$ 操作后，$b=[36,25,16,9,4]$；
第二次 $6$ 操作后，$b=[36,25,52,34,20]$。
容易证明不存在一个合法选择使得 $x\lt 6$。
数据范围与约定
本题目采用 $\text{subtask}$ 测试。
按照惯例，规定 ${0^0=1}$。
对于 $100\%$ 的数据，$1\le n\le 10^5$，$k\in{\left\{0,1,2\right\}}$，$1\le a_i\le 10^5$，$1\le m\le 10^6$。
具体数据范围如下：
$\text{subtask 1(05pts)}$：$k=0$，$1\le n,a_i\le 5$；
$\text{subtask 2(15pts)}$：$k=0$；
$\text{subtask 3(10pts)}$：$k=1$，$1\le n,a_i\le 1000$；
$\text{subtask 4(20pts)}$：$k=1$；
$\text{subtask 5(20pts)}$：$k=2$，$1\le n,a_i\le 1000$；
$\text{subtask 6(30pts)}$：$k=2$。
