Masala C

Sizning bog‘ingiz bo‘ylab chapdan o‘ngga qarab ketadigan uzunligi N bo‘lgan sug‘orish kanali bor. Kanal \(N\) ta ketma-ket bo‘limdan iborat (har biri 1 metr). Har bir bo‘limning hozirgi balandligi \(h[1], h[2], ..., h[N]\) metr.

Siz kanalni bir xil balandlikda qilishni xohlaysiz, ya’ni hamma bo‘limlar balandligini aynan \(H\) ga keltirmoqchisiz.

Buning uchun sizda “shlyuz”li texnika bor: u chapdan o‘ngga yuradi va ortiqcha tuproqni o‘zi bilan olib ketishi mumkin.

• Siz oldindan bitta natural son \(H\) ni tanlaysiz.
• Dastlab texnikada olib yurilayotgan tuproq miqdori \(C = 0\).
• Texnika i-bo‘limga kelganda:

1. Agar \(h[i] \ge H\) bo‘lsa, ortiqcha tuproq \(h[i] - H\) kesib olinadi va zaxiraga qo‘shiladi:
   \(C += h[i] - H\). Bo‘lim balandligi \(H\) bo‘lib qoladi.
2. Agar \(h[i] < H\) bo‘lsa, bo‘limni \(H\) ga ko‘tarish uchun zaxiradan \(H - h[i]\) tuproq to‘kiladi.
   Bu faqat \(C \ge H - h[i]\) bo‘lsa mumkin. So‘ng \(C -= H - h[i]\) va bo‘lim balandligi \(H\) bo‘ladi.

Oxirida zaxirada qolgan tuproq sizni qiziqtirmaydi — u kanal oxiridagi daryoga to‘kilib ketadi.

Vazifa: shunday eng katta \(H\) ni topingki, texnika chapdan o‘ngga yurib, hech qachon zaxirasi yetmay qolmasdan, barcha bo‘limlarni aynan H balandlikka keltira olsin.

Subtasklar

- Subtask 1 (7 ball): \(h\) massiv o'suvchi. 

- Subtask 2 (38 ball): \(N \le 200\)

- Subtask 3 (55 ball): Qo'shimcha cheklovlarsiz.

Birinchi qatorda - \((1\le N \le 10^6)\)

Ikkinchi qatorda massiv elementlari kiritiladi. \((1\le i \le n, 1\le h[i] \le 10^9)\)

Bitta natural son - erishish mumkin bo'lgan maksimal \(H\)