题目描述

给定一个长度为 $n$ 的序列 $a$ 和两个参数 $m$、$k$。

现在另有一个长度为 $n$ 的序列 $b$。最开始 $b$ 中的每一个元素均为 $0$。

称如下为一个 $x$ 操作（$x\ge 0$）：

1. 选定一个整数 $i$，满足 $1\le i\le n$。
2. 对于 $\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$。