{"raw_statement":[{"iden":"statement","content":"Instructors of Some Informatics School make students go to bed.\n\nThe 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.\n\nThe 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.\n\nWhen 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.\n\nWhile 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.\n\nFormally, here is what's happening:\n\n*   A curfew is announced, at this point in room _i_ there are _a__i_ students.\n*   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.\n*   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).\n*   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.\n*   Instructors move from room 1 to room 2 and from room _n_ to room _n_ - 1.\n*   This process continues until all rooms are processed.\n\nLet _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."},{"iden":"input","content":"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.\n\nThe 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.\n\nIt is guaranteed that _a_1 + _a_2 + ... + _a__n_ = _nb_."},{"iden":"output","content":"Output one integer, the minimal possible value of the maximum of _x__i_."},{"iden":"examples","content":"Input\n\n5 1 1\n1 0 0 0 4\n\nOutput\n\n1\n\nInput\n\n6 1 2\n3 8 0 1 0 0\n\nOutput\n\n2"},{"iden":"note","content":"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.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"信息学学校的辅导员会督促学生回宿舍睡觉。\n\n宿舍楼共有 #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] 名辅导员。\n\n宵禁执行过程如下：一名辅导员从第 #cf_span[1] 个房间出发，向第 #cf_span[n] 个房间移动；另一名辅导员从第 #cf_span[n] 个房间出发，向第 #cf_span[1] 个房间移动。处理完当前房间后，每位辅导员继续前往下一个房间。两名辅导员同时进入房间并移动，若 #cf_span[n] 为奇数，则仅第一位辅导员处理中间的房间。当所有房间都被处理后，过程结束。\n\n当辅导员处理一个房间时，她会统计房间内学生的数量，然后关灯并锁门。如果该房间内的学生数量不等于 #cf_span[b]，她会将该房间的编号记入自己的笔记本（然后关灯并锁门）。辅导员们急于准备第二天的教学计划，因此她们只关心学生人数，而不关心具体是谁。\n\n在辅导员进入房间期间，学生可以在尚未被锁且未被处理的房间之间移动。一名学生最多可以移动 #cf_span[d] 个房间，即她可以移动到编号与当前房间相差不超过 #cf_span[d] 的房间。此外，学生在移动后（或代替移动）可以选择躲在所在房间的床下。此时，辅导员在清点时不会计入该学生。每个房间可以同时容纳任意数量的学生躲藏。\n\n形式化地，过程如下：\n\n设 #cf_span[x1] 表示第一位辅导员统计到非躲藏学生数量不等于 #cf_span[b] 的房间数，#cf_span[x2] 表示第二位辅导员的相应数量。学生知道校长只会听取一份投诉，因此他们希望最小化 #cf_span[xi] 的最大值。请帮助他们找出这个最小可能值，假设他们采用最优策略。\n\n第一行包含三个整数 #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])，分别表示宿舍楼的房间数、学生最大移动距离、每个房间的官方人数。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 109])，第 #cf_span[i] 个数表示宵禁前第 #cf_span[i] 个房间的学生人数。\n\n保证 #cf_span[a1 + a2 + ... + an = nb]。\n\n请输出一个整数，表示 #cf_span[xi] 最大值的最小可能值。\n\n在第一个样例中，前三个房间由第一位辅导员处理，后两个房间由第二位辅导员处理。一种最优策略如下：首先，三名学生从第 #cf_span[5] 个房间移动到第 #cf_span[4] 个房间；接着，其中两人移动到第 #cf_span[3] 个房间，其中一人躲藏在床下。这样，第一位辅导员记录下第 #cf_span[2] 个房间，第二位辅导员无记录。\n\n在第二个样例中，一种最优策略如下：首先，第 #cf_span[1] 个房间的所有学生躲藏，第 #cf_span[2] 个房间的所有学生移动到第 #cf_span[3] 个房间；接着，一名学生从第 #cf_span[3] 个房间移动到第 #cf_span[4] 个房间，五名学生躲藏。这样，第一位辅导员记录下第 #cf_span[1] 和第 #cf_span[2] 个房间，第二位辅导员记录下第 #cf_span[5] 和第 #cf_span[6] 个房间。"},{"iden":"input","content":"第一行包含三个整数 #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]。"},{"iden":"output","content":"输出一个整数，表示 #cf_span[xi] 最大值的最小可能值。"},{"iden":"examples","content":"输入\n5 1 1\n1 0 0 0 4\n输出\n1\n\n输入\n6 1 2\n3 8 0 1 0 0\n输出\n2"},{"iden":"note","content":"在第一个样例中，前三个房间由第一位辅导员处理，后两个房间由第二位辅导员处理。一种最优策略如下：首先，三名学生从第 #cf_span[5] 个房间移动到第 #cf_span[4] 个房间；接着，其中两人移动到第 #cf_span[3] 个房间，其中一人躲藏在床下。这样，第一位辅导员记录下第 #cf_span[2] 个房间，第二位辅导员无记录。\n\n在第二个样例中，一种最优策略如下：首先，第 #cf_span[1] 个房间的所有学生躲藏，第 #cf_span[2] 个房间的所有学生移动到第 #cf_span[3] 个房间；接着，一名学生从第 #cf_span[3] 个房间移动到第 #cf_span[4] 个房间，五名学生躲藏。这样，第一位辅导员记录下第 #cf_span[1] 和第 #cf_span[2] 个房间，第二位辅导员记录下第 #cf_span[5] 和第 #cf_span[6] 个房间。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, d, b \\in \\mathbb{Z}^+ $: number of rooms, maximum running distance per student, and required students per room.  \nLet $ A = (a_1, a_2, \\dots, a_n) \\in \\mathbb{Z}_{\\geq 0}^n $ be the initial student count per room, with $ \\sum_{i=1}^n a_i = n \\cdot b $.  \n\nTwo instructors move simultaneously:  \n- Instructor 1 starts at room 1, moves right to room $ n $.  \n- Instructor 2 starts at room $ n $, moves left to room 1.  \n- If $ n $ is odd, the middle room $ \\left\\lceil \\frac{n}{2} \\right\\rceil $ is processed only by Instructor 1.  \n\nEach instructor, upon entering room $ i $, counts non-hidden students and records $ i $ if the count $ \\neq b $.  \n\nStudents may:  \n- Move to any room $ j $ such that $ |i - j| \\leq d $, before the instructor enters either room.  \n- Hide under a bed in any room they occupy (unlimited hiding capacity).  \n\nLet $ x_1 $ = number of rooms (processed by Instructor 1) with non-hidden count $ \\neq b $.  \nLet $ x_2 $ = number of rooms (processed by Instructor 2) with non-hidden count $ \\neq b $.  \n\n**Constraints**  \n1. $ 2 \\leq n \\leq 100{,}000 $  \n2. $ 1 \\leq d \\leq n-1 $  \n3. $ 1 \\leq b \\leq 10{,}000 $  \n4. $ 0 \\leq a_i \\leq 10^9 $ for all $ i $  \n5. $ \\sum_{i=1}^n a_i = n \\cdot b $  \n\n**Objective**  \nMinimize $ \\max(x_1, x_2) $ over all valid student movement and hiding strategies.","simple_statement":null,"has_page_source":false}