Castle Defense

오늘 당신은 분노한 오크 군대의 공격을 받는 성을 방어하기 위해 엘프 궁수 무리를 지휘한다. 성의 세 면은 통과할 수 없는 산으로 보호되어 있고, 나머지 한 면에는 n개의 구역으로 나뉜 긴 성벽이 자리한다. 현재 이 성벽의 i-th 구역에는 정확히 ai명의 궁수가 배치되어 있다. 구역 i에 서 있는 궁수는 거리가 r를 초과하지 않는 구역을 공격하는 오크를 쏠 수 있다. 즉, |i - j| ≤ r인 모든 구역 j가 이에 해당한다. 특히 r = 0은 궁수들이 구역 i를 공격하는 오크만 쏠 수 있음을 뜻한다.

구역 i의 방어 수준을 이 구역을 공격하는 오크를 쏠 수 있는 궁수의 총수로 정의한다. 방어 계획의 신뢰도는 성벽의 개별 구역별 방어 수준 중 최솟값이다.

공격까지 시간이 얼마 남지 않았으므로 성벽에 이미 배치된 궁수들을 재배치할 수는 없다. 하지만 성벽 구역들에 임의의 방식으로 배치할 수 있는 예비 궁수 k명이 있다. 방어 계획의 신뢰도를 가능한 한 최대로 만들고자 한다.

입력의 첫째 줄에는 세 정수 n, r, k (1 ≤ n ≤ 500 000, 0 ≤ r ≤ n, 0 ≤ k ≤ 1018)가 주어진다. 각각 성벽 구역의 수, 궁수가 다른 구역까지 쏠 수 있는 최대 거리, 아직 성벽에 배치하지 않은 궁수의 수를 나타낸다. 둘째 줄에는 각 구역에 현재 배치된 궁수의 수를 나타내는 n개의 정수 a1, a2, ..., (0 ≤ ai ≤ 109)이 주어진다.

정수 하나를 출력한다. 이 값은 방어 계획에서 가능한 최대 신뢰도, 즉 추가 궁수 k명을 최적으로 배치했을 때 가능한 최소 방어 수준의 최댓값이다.