CF949D.Curfew

Instructors of Some Informatics School make students go to bed.

The house contains n rooms, in each room exactly b students were supposed to sleep. However, at the time of curfew it happened that many students are not located in their assigned rooms. The rooms are arranged in a row and numbered from 1 to n. Initially, in i-th room there are a__i students. All students are currently somewhere in the house, therefore _a_1 + _a_2 + ... + a__n = nb. Also 2 instructors live in this house.

The process of curfew enforcement is the following. One instructor starts near room 1 and moves toward room n, while the second instructor starts near room n and moves toward room 1. After processing current room, each instructor moves on to the next one. Both instructors enter rooms and move simultaneously, if n is odd, then only the first instructor processes the middle room. When all rooms are processed, the process ends.

When an instructor processes a room, she counts the number of students in the room, then turns off the light, and locks the room. Also, if the number of students inside the processed room is not equal to b, the instructor writes down the number of this room into her notebook (and turns off the light, and locks the room). Instructors are in a hurry (to prepare the study plan for the next day), so they don't care about who is in the room, but only about the number of students.

While instructors are inside the rooms, students can run between rooms that are not locked and not being processed. A student can run by at most d rooms, that is she can move to a room with number that differs my at most d. Also, after (or instead of) running each student can hide under a bed in a room she is in. In this case the instructor will not count her during the processing. In each room any number of students can hide simultaneously.

Formally, here is what's happening:

• A curfew is announced, at this point in room i there are a__i students.
• Each student can run to another room but not further than d rooms away from her initial room, or stay in place. After that each student can optionally hide under a bed.
• Instructors enter room 1 and room n, they count students there and lock the room (after it no one can enter or leave this room).
• Each student from rooms with numbers from 2 to n - 1 can run to another room but not further than d rooms away from her current room, or stay in place. Each student can optionally hide under a bed.
• Instructors move from room 1 to room 2 and from room n to room n - 1.
• This process continues until all rooms are processed.

Let _x_1 denote the number of rooms in which the first instructor counted the number of non-hidden students different from b, and _x_2 be the same number for the second instructor. Students know that the principal will only listen to one complaint, therefore they want to minimize the maximum of numbers x__i. Help them find this value if they use the optimal strategy.

某信息学学校的学生被老师要求按时就寝。

这栋宿舍楼共有 $n$ 个房间，每个房间本应恰好住 $b$ 名学生。然而，在宵禁时刻到来时，许多学生并未待在自己被分配的房间中。这些房间排成一列，编号从 $1$ 到 $n$。初始时，第 $i$ 个房间中有 $a_i$ 名学生。所有学生此时都在楼内，因此满足 $a_1 + a_2 + \dots + a_n = nb$。此外，楼内还住着两位老师。

宵禁执行过程如下：一位老师从房间 $1$ 出发，向房间 $n$ 移动；另一位老师则从房间 $n$ 出发，向房间 $1$ 移动。每位老师处理完当前房间后，便前往下一个房间。两位老师同时进入房间并同步移动；若 $n$ 为奇数，则中间房间（即房间 $\frac{n+1}{2}$）仅由第一位老师处理。当所有房间均被处理完毕后，整个过程结束。

当一位老师处理某个房间时，她会清点该房间内的学生人数，随后关灯并锁门。此外，若该房间内学生人数不等于 $b$，这位老师会在自己的笔记本上记下该房间的编号（之后同样关灯并锁门）。老师们非常匆忙（要为第二天制定学习计划），因此她们并不关心房间内具体是哪些学生，只关心学生人数。

在老师进入房间期间，学生可以在尚未被锁上且未被处理的房间之间奔跑。一名学生最多可奔跑 $d$ 个房间的距离，即她可移动至编号与当前房间编号之差的绝对值不超过 $d$ 的房间。此外，每名学生在奔跑之后（或不奔跑而直接）还可选择躲到所在房间的床下；此时老师在清点人数时将无法发现她。每个房间可同时容纳任意数量的学生躲藏。

形式化地，整个过程如下：

• 宵禁指令发布，此时第 $i$ 个房间中有 $a_i$ 名学生；
• 每名学生可奔跑至与其初始房间编号之差的绝对值不超过 $d$ 的另一房间，或留在原地；之后每名学生可选择是否躲到床下；
• 两位老师分别进入房间 $1$ 和房间 $n$，清点其中学生人数，并锁门（此后无人能进出这两个房间）；
• 所有位于编号为 $2$ 至 $n-1$ 的房间中的学生，均可奔跑至与其当前房间编号之差的绝对值不超过 $d$ 的另一房间，或留在原地；之后每名学生可选择是否躲到床下；
• 两位老师分别从房间 $1$ 移至房间 $2$，以及从房间 $n$ 移至房间 $n-1$；
• 此过程持续进行，直至所有房间均被处理完毕。

令 $x_1$ 表示第一位老师所处理的房间中，未躲藏的学生人数不等于 $b$ 的房间数量；类似地，令 $x_2$ 表示第二位老师所处理的房间中，未躲藏的学生人数不等于 $b$ 的房间数量。学生们知道校长只会听取一份投诉，因此他们希望最小化 $\max\{x_1, x_2\}$。请你在学生采用最优策略的前提下，帮助他们求出该最小值。

The first line contains three integers n, d and b (2 ≤ n ≤ 100 000, 1 ≤ d ≤ n - 1, 1 ≤ b ≤ 10 000), number of rooms in the house, running distance of a student, official number of students in a room.

The second line contains n integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 109), i-th of which stands for the number of students in the i-th room before curfew announcement.

It is guaranteed that _a_1 + _a_2 + ... + a__n = nb.

第一行包含三个整数 $n$、$d$ 和 $b$（$2 \leq n \leq 100\,000$，$1 \leq d \leq n - 1$，$1 \leq b \leq 10\,000$），分别表示房屋中的房间数、一名学生的最大奔跑距离、每间房间的官方学生人数。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$0 \leq a_i \leq 10^9$），其中第 $i$ 个数表示宵禁通知发布前第 $i$ 间房间中的学生人数。

保证 $a_1 + a_2 + \dots + a_n = nb$。

Output one integer, the minimal possible value of the maximum of x__i.

输出一个整数，即 $x_i$ 的最大值的最小可能值。

In the first sample the first three rooms are processed by the first instructor, and the last two are processed by the second instructor. One of the optimal strategies is the following: firstly three students run from room 5 to room 4, on the next stage two of them run to room 3, and one of those two hides under a bed. This way, the first instructor writes down room 2, and the second writes down nothing.

In the second sample one of the optimal strategies is the following: firstly all students in room 1 hide, all students from room 2 run to room 3. On the next stage one student runs from room 3 to room 4, and 5 students hide. This way, the first instructor writes down rooms 1 and 2, the second instructor writes down rooms 5 and 6.

在第一个样例中，前三个房间由第一位监考老师负责，后两个房间由第二位监考老师负责。一种最优策略如下：首先，三名学生从房间 5 跑到房间 4；在下一阶段，其中两人继续跑到房间 3，另一人则藏到床下。这样，第一位监考老师记录的房间为 2，第二位监考老师未记录任何房间。

在第二个样例中，一种最优策略如下：首先，房间 1 中的所有学生都藏起来，房间 2 中的所有学生都跑到房间 3；在下一阶段，一名学生从房间 3 跑到房间 4，其余 5 名学生藏起来。这样，第一位监考老师记录的房间为 1 和 2，第二位监考老师记录的房间为 5 和 6。