今天你将带领一群精灵弓箭手保卫被愤怒的兽人大军攻击的城堡。城堡的三侧被无法逾越的山脉所保护,剩下的一侧则被一堵分成n段的长墙占据。此时,这堵墙的第i段正好有ai个弓箭手。你知道,站在 i 区域的弓箭手可以射杀攻击距离不超过 r 区域的兽人,也就是 |i - j| 的所有 j 区域。 ≤ r。特别是,r = 0 意味着弓箭手只能射击攻击 i 部分的兽人。
将第 i 部分的防御等级表示为能够向攻击该部分的兽人射击的弓箭手总数。防御方案的可靠性是指单个墙段的防御水平的最小值。
距离攻击还有一点时间,所以你无法重新分配已经位于城墙上的弓箭手。但是,有 k 个弓箭手储备,您可以以任意方式将其分布在墙段之间。您希望防御计划获得最大程度的可靠性。
输入
输入的第一行包含三个整数 n、r 和 k (1 ≤ n ≤ 500 000, 0 ≤ r ≤ n, 0 ≤ k ≤ 1018) - 墙的部分数、与其他部分弓箭手仍然可以射击的最大距离以及尚未沿墙分布的弓箭手数量。第二行包含 n 个整数 a1, a2, ..., an (0 ≤ ai ≤ 109) – 每个部分当前的弓箭手数量。
输出
打印一个整数——防御计划可靠性的最大可能值,即如果我们以最佳方式分配 k 个额外弓箭手,则最小防御级别的最大可能值。
示例
输入 #1
5 0 6 5 4 3 4 9
输出 #1
5
输入 #2
4 2 0 1 2 3 4
输出 #2
6
输入 #3
5 1 1 2 1 2 1 2
输出 #3
3