Giờ giới nghiêm

Một ký túc xá có $n$ phòng xếp thành một hàng, đánh số từ $1$ đến $n$. Theo quy định, mỗi phòng phải có đúng $b$ học sinh ngủ lại. Tuy nhiên, vào thời điểm kiểm tra giờ giới nghiêm, phòng thứ $i$ đang có $a_i$ học sinh. Tất cả học sinh đều đang ở trong ký túc xá, nên $a_1+a_2+\dots +a_n=n·b$.

Có hai giám thị đi kiểm tra. Giám thị thứ nhất bắt đầu từ phòng $1$ và đi về phía phòng $n$, giám thị thứ hai bắt đầu từ phòng $n$ và đi về phía phòng $1$. Hai người di chuyển và kiểm tra đồng thời: ở bước thứ $k$, giám thị thứ nhất kiểm tra phòng $k$ còn giám thị thứ hai kiểm tra phòng $n-k+1$. Nếu $n$ lẻ thì phòng ở chính giữa chỉ do giám thị thứ nhất kiểm tra. Quá trình kết thúc khi mọi phòng đã được kiểm tra.

Khi kiểm tra một phòng, giám thị đếm số học sinh đang có mặt (không tính những người đang trốn), rồi khoá phòng lại. Nếu số học sinh đếm được khác $b$, giám thị ghi số hiệu phòng đó vào sổ.

Trong lúc các giám thị đang kiểm tra, học sinh có thể chạy giữa các phòng chưa bị khoá và chưa bị kiểm tra. Cụ thể, quá trình diễn ra như sau:

• Hiệu lệnh giới nghiêm vang lên, lúc này phòng $i$ có $a_i$ học sinh.
• Mỗi học sinh có thể chạy sang một phòng khác cách phòng hiện tại không quá $d$ đơn vị (hoặc đứng yên). Sau đó mỗi học sinh có thể chui xuống gầm giường để trốn; giám thị sẽ không đếm những học sinh đang trốn. Số học sinh trốn trong một phòng là không giới hạn.
• Hai giám thị bước vào phòng $1$ và phòng $n$, đếm số học sinh rồi khoá phòng lại.
• Các học sinh ở những phòng chưa bị khoá lại được chạy tiếp không quá $d$ đơn vị và có thể trốn.
• Hai giám thị đi sang phòng tiếp theo, và quá trình lặp lại cho tới khi hết phòng.

Gọi $x_1$ là số phòng mà giám thị thứ nhất ghi vào sổ, $x_2$ là số phòng mà giám thị thứ hai ghi vào sổ. Ban giám hiệu chỉ xử lý một quyển sổ duy nhất, nên các học sinh muốn giá trị $max(x_1,x_2)$ càng nhỏ càng tốt.

Hãy tìm giá trị nhỏ nhất của $max(x_1,x_2)$ khi các học sinh phối hợp một cách tối ưu.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $d$, $b$: số phòng, khoảng cách tối đa một học sinh chạy được trong mỗi lượt, và số học sinh quy định cho mỗi phòng.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$: số học sinh đang có ở mỗi phòng trước khi có hiệu lệnh.

Dữ liệu ra

Một số nguyên duy nhất là giá trị nhỏ nhất có thể của $max(x_1,x_2)$.

Ràng buộc

• $2\le n\le 100000$
• $1\le d\le n-1$
• $1\le b\le 10000$
• $0\le a_i\le {10}^9$
• $a_1+a_2+\dots +a_n=n·b$

Ví dụ