Masala E

Bog‘da \(N\) ta olma daraxti bo‘lib, ular \(1\) dan \(N\) gachа raqamlangan. Daraxtlar halqa ko‘rinishida joylashgan: ya’ni \(i-\) daraxt \(i+1-\)daraxt bilan \((1 ≤ i ≤ n − 1)\) qo'shni, shuningdek \(N-\) va \(1-\) daraxt ham qo'shnilar hisoblanadi. \(i-\) daraxtdagi mevalar soni \(a_i\) ga teng.
Bog' egasi Shohruh va Azizbekka mevalarni terish vazifasi topshirildi. Shohruh ham Azizbek ham qaysidir daraxtdan mevalarni terishni boshlaydi. Shohruh o'zi tanlagan daraxtdagi mevalarni terib bo'lgach, oldin o'zi mevasini tergan daraxtlariga qo'shni bo'lgan istalgan daraxtni tanlaydi va ularni ham teradi. Istalgan daraxtdagi mevani terish 1 soat vaqt oladi. Xuddi shu qoidalar Azizbek uchun ham amal qiladi. Agar oxirida bitta daraxt qolsa, uni Shohruh teradi. Qaysi daraxtdagi mevani terishni birinchi bo'lib Shohruh tanlasa hamda Shohruh ham, Azizbek ham optimal o'ynasa Shohruh ko'pi bilan qancha olma terishi mumkinligi aniqlang.

Birinchi qatorda musbat butun son \(N \ (2 \le N \le 5000)\) — olma daraxtlari soni beriladi. 

Ikkinchi qatorda \(N\) ta butun son \(a_1, a_2, ..., a_n \ (1 \le a_i \le 2000)\) — har bir daraxtdagi mevalar soni kiritiladi.

Yagona satrda Shohruh terishi mumkin bo‘lgan maksimal olmalar sonini chop eting.