题目内容

产线走廊上排着 $q$ 只温感探头，第 $j$ 只当前读数记为 $h_j$。值班员最多可以出门巡检 $t$ 回。每一回先定下一个起点 $p$（满足 $1\le p\le q-w+1$），再把从第 $p$ 只到第 $p+w-1$ 只这连续 $w$ 只探头的显示值各抬高一档。

请在出门次数不超过 $t$ 的限制下，让整排探头显示值里最低的那一档尽量升高，并给出这个最低档最终能升到的最高水平。

输入描述

第一行三个整数 $q,w,t$（$1\le q\le 2\times 10^5$，$1\le w\le q$，$0\le t\le 10^9$）。

第二行 $q$ 个整数 $h_1,h_2,\dots,h_q$（$|h_j|\le 10^9$）。

输出描述

输出一个整数，即整排最低显示值在限制内能够升到的最高水平。

样例1

输入

6 3 5
4 1 2 0 3 5

输出

4

说明

读数为 $4,1,2,0,3,5$，每一回覆盖 $3$ 只，最多巡检 $5$ 回。

若要把最低档升到 $4$：第 $2$ 只当前是 $1$，还差 $3$。从第 $2$ 只起做 $3$ 回覆盖，作用在第 $2\sim 4$ 只上，得到 $4,4,5,3,3,5$。第 $4$ 只还差 $1$，再从第 $4$ 只起覆盖 $1$ 回（第 $4\sim 6$ 只），得到 $4,4,5,4,4,6$，最低档为 $4$，共用 $4$ 回。

若想升到 $5$：按同样方式从左到右补齐，次数会超过 $5$，故 $5$ 做不到。答案为 $4$。