CF954G.Castle Defense

Today you are going to lead a group of elven archers to defend the castle that is attacked by an army of angry orcs. Three sides of the castle are protected by impassable mountains and the remaining side is occupied by a long wall that is split into n sections. At this moment there are exactly a__i archers located at the i-th section of this wall. You know that archer who stands at section i can shoot orcs that attack section located at distance not exceeding r, that is all such sections j that |i - j| ≤ r. In particular, r = 0 means that archers are only capable of shooting at orcs who attack section i.

Denote as defense level of section i the total number of archers who can shoot at the orcs attacking this section. Reliability of the defense plan is the minimum value of defense level of individual wall section.

There is a little time left till the attack so you can't redistribute archers that are already located at the wall. However, there is a reserve of k archers that you can distribute among wall sections in arbitrary way. You would like to achieve maximum possible reliability of the defence plan.

今天，你将率领一支精灵弓箭手小队，守卫正遭受愤怒兽人军队进攻的城堡。城堡三面被不可逾越的山脉所保护，剩余一面则是一道长墙，被划分为 $n$ 个区段。此时，第 $i$ 个区段上恰好有 $a_i$ 名弓箭手驻守。已知驻守在第 $i$ 个区段的弓箭手能够射杀进攻距离不超过 $r$ 的区段上的兽人，即所有满足 $|i - j| \leq r$ 的区段 $j$ 上的兽人。特别地，当 $r = 0$ 时，弓箭手仅能攻击正在进攻其所在区段 $i$ 的兽人。

定义第 $i$ 个区段的防御等级为：能够射击进攻该区段之兽人的弓箭手总数。整个防御方案的可靠性定义为所有墙区段中防御等级的最小值。

距离进攻开始所剩时间极少，因此你无法重新调配已部署在墙上的弓箭手。但你手中尚有 $k$ 名预备弓箭手，可将其以任意方式分配至各墙区段。你的目标是使防御方案的可靠性尽可能最大化。

The first line of the input contains three integers n, r and k (1 ≤ n ≤ 500 000, 0 ≤ r ≤ n, 0 ≤ k ≤ 1018) — the number of sections of the wall, the maximum distance to other section archers can still shoot and the number of archers yet to be distributed along the wall. The second line contains n integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 109) — the current number of archers at each section.

输入的第一行包含三个整数 $n$、$r$ 和 $k$（$1 ≤ n ≤ 500\,000$，$0 ≤ r ≤ n$，$0 ≤ k ≤ 10^{18}$）——分别表示城墙的段数、弓箭手仍能射击到的最远距离（以段数计），以及尚待沿城墙部署的弓箭手数量。
第二行包含 $n$ 个整数 $a_1,\,a_2,\,...,\,a_n$（$0 ≤ a_i ≤ 10^9$）——表示每一段当前已有的弓箭手数量。

Print one integer — the maximum possible value of defense plan reliability, i.e. the maximum possible value of minimum defense level if we distribute k additional archers optimally.

输出一个整数——防御计划可靠性的最大可能值，即在最优分配 $k$ 名额外弓箭手的前提下，最小防御等级的最大可能值。