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.
## Input
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_.
## Output
Output one integer, the minimal possible value of the maximum of _x__i_.
[samples]
## Note
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.
某信息学学校的辅导员会督促学生就寝。
宿舍楼共有 #cf_span[n] 个房间，每个房间本应安排 #cf_span[b] 名学生住宿。然而，在宵禁时，许多学生并未在自己的指定房间内。房间排成一行，编号从 #cf_span[1] 到 #cf_span[n]。初始时，第 #cf_span[i] 个房间中有 #cf_span[ai] 名学生。所有学生目前都在楼内，因此 #cf_span[a1 + a2 + ... + an = nb]。此外，楼内还有 #cf_span[2] 名辅导员。
宵禁执行过程如下：一名辅导员从第 #cf_span[1] 个房间出发，向第 #cf_span[n] 个房间移动；另一名辅导员从第 #cf_span[n] 个房间出发，向第 #cf_span[1] 个房间移动。每处理完一个房间后，每位辅导员继续前往下一个房间。两名辅导员同时进入房间并移动，若 #cf_span[n] 为奇数，则仅第一位辅导员处理中间的房间。当所有房间都被处理完毕后，过程结束。
当辅导员处理一个房间时，她会统计房间内学生的数量，然后关闭灯光并锁门。如果该房间内的学生数量不等于 #cf_span[b]，她会将该房间的编号记入自己的笔记本（然后关闭灯光并锁门）。辅导员们急于准备第二天的学习计划，因此她们并不关心具体是谁在房间内，只关心学生人数。
在辅导员进入房间期间，学生可以在未被锁住且未被处理的房间之间移动。一名学生最多可以移动 #cf_span[d] 个房间，即她可以移动到编号与当前房间相差至多 #cf_span[d] 的房间。此外，学生在移动后（或代替移动）可以选择躲在所处房间的床下。此时，辅导员在清点人数时不会计入该学生。每个房间中可以同时有任意数量的学生躲藏。
形式化地，流程如下：
设 #cf_span[x1] 表示第一位辅导员统计到非躲藏学生数量不等于 #cf_span[b] 的房间数，#cf_span[x2] 表示第二位辅导员的相应数量。学生知道校长只会听取一份投诉，因此他们希望最小化 #cf_span[xi] 的最大值。请帮助他们找出在采用最优策略时该最大值的最小可能值。
第一行包含三个整数 #cf_span[n], #cf_span[d] 和 #cf_span[b]（#cf_span[2 ≤ n ≤ 100 000], #cf_span[1 ≤ d ≤ n - 1], #cf_span[1 ≤ b ≤ 10 000]），分别表示宿舍楼的房间数、学生最大移动距离和每个房间应有学生数。
第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 109]），第 #cf_span[i] 个数表示宵禁前第 #cf_span[i] 个房间中的学生人数。
保证 #cf_span[a1 + a2 + ... + an = nb]。
请输出一个整数，表示 #cf_span[xi] 最大值的最小可能值。
在第一个样例中，前三个房间由第一位辅导员处理，后两个房间由第二位辅导员处理。一种最优策略如下：首先，三名学生从第 #cf_span[5] 个房间移动到第 #cf_span[4] 个房间；下一阶段，其中两人移动到第 #cf_span[3] 个房间，而这两人中有一人躲藏在床下。这样，第一位辅导员记录了房间 #cf_span[2]，第二位辅导员未记录任何房间。
在第二个样例中，一种最优策略如下：首先，第 #cf_span[1] 个房间的所有学生躲藏，第 #cf_span[2] 个房间的所有学生移动到第 #cf_span[3] 个房间；下一阶段，一名学生从第 #cf_span[3] 个房间移动到第 #cf_span[4] 个房间，另外 #cf_span[5] 名学生躲藏。这样，第一位辅导员记录了房间 #cf_span[1] 和 #cf_span[2]，第二位辅导员记录了房间 #cf_span[5] 和 #cf_span[6]。
## Input
第一行包含三个整数 #cf_span[n], #cf_span[d] 和 #cf_span[b]（#cf_span[2 ≤ n ≤ 100 000], #cf_span[1 ≤ d ≤ n - 1], #cf_span[1 ≤ b ≤ 10 000]），分别表示宿舍楼的房间数、学生最大移动距离和每个房间应有学生数。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[0 ≤ ai ≤ 109]），第 #cf_span[i] 个数表示宵禁前第 #cf_span[i] 个房间中的学生人数。保证 #cf_span[a1 + a2 + ... + an = nb]。
## Output
输出一个整数，表示 #cf_span[xi] 最大值的最小可能值。
[samples]
## Note
在第一个样例中，前三个房间由第一位辅导员处理，后两个房间由第二位辅导员处理。一种最优策略如下：首先，三名学生从第 #cf_span[5] 个房间移动到第 #cf_span[4] 个房间；下一阶段，其中两人移动到第 #cf_span[3] 个房间，而这两人中有一人躲藏在床下。这样，第一位辅导员记录了房间 #cf_span[2]，第二位辅导员未记录任何房间。
在第二个样例中，一种最优策略如下：首先，第 #cf_span[1] 个房间的所有学生躲藏，第 #cf_span[2] 个房间的所有学生移动到第 #cf_span[3] 个房间；下一阶段，一名学生从第 #cf_span[3] 个房间移动到第 #cf_span[4] 个房间，另外 #cf_span[5] 名学生躲藏。这样，第一位辅导员记录了房间 #cf_span[1] 和 #cf_span[2]，第二位辅导员记录了房间 #cf_span[5] 和 #cf_span[6]。
**Definitions**
Let $ n, d, b \in \mathbb{Z}^+ $: number of rooms, maximum student movement distance, and target students per room.
Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}_{\geq 0}^n $: initial student counts per room, with $ \sum_{i=1}^n a_i = n b $.
Two instructors move simultaneously:
- Instructor 1: processes rooms $ 1, 2, \dots, \lceil n/2 \rceil $ in order.
- Instructor 2: processes rooms $ n, n-1, \dots, \lfloor n/2 \rfloor + 1 $ in order.
A student in room $ i $ at time of curfew can:
- Move to any room $ j $ such that $ |i - j| \leq d $, **before** either instructor enters either room.
- Hide under a bed in any room she is in (at the moment of processing), avoiding count.
Let $ x_1 $: number of rooms processed by Instructor 1 with non-hidden student count $ \neq b $.
Let $ x_2 $: same for Instructor 2.
**Constraints**
1. $ 2 \leq n \leq 100{,}000 $
2. $ 1 \leq d \leq n-1 $
3. $ 1 \leq b \leq 10{,}000 $
4. $ 0 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
5. $ \sum_{i=1}^n a_i = n b $
**Objective**
Minimize $ \max(x_1, x_2) $ over all valid student movement and hiding strategies.