Masala #BXZ1JNPRC1

Robolandiya ko'chasi bo'ylab n ta osmono'par binolar bir qatorda joylashgan. \(i-\) binoning balandligi \(T_i\), har bir osmono‘par binoning kengligi esa 1 ga teng.

Azizbek - Robolus kompaniyasining marketing bo'limi boshlig'i. Robolus marketing faoliyati doirasida, Robolus osmono'par binolarning old devoriga plyus shaklidagi plakat (Robolus logotipi) ko'rinishidagi mumkin bo'lgan eng katta reklamani joylashtirishga qaror qildi: to'rtta qo'l (chapga, o'ngga, yuqoriga va pastga, osmono'par binolarning chetiga perpendikulyar). Azizbek mumkin bo'lgan eng katta uzunlikdagi plus shaklidagi bannerni yopishtirmoqchi. Albatta, butun reklama osmono'par binolarga yopishtirilgan bo'lishi kerak, aks holda shamol unga zarar etkazishi va kompaniya marketingga yomon ta'sir qilishi mumkin.

Quyidagi namunaga qarang:

T = {6, 5, 4, 6, 3, 5, 2}, L = 2

Ushbu namuna uchun javob L = 2, chunki, tepa, past, o'ng va chap tomonga 2 birlikdagi “qanot” lar chiqqan. Azizbek bannerni imkon qadar kattaroq bo'lishini xohlaydi. Unga L ning eng katta qiymatini aniqlashga yordam bering.

Birinchi qatorda N - binolar soni kiritiladi.

Keyingi qatorda N ta butun son \(T_i\) - har bir bino balandligi kiritiladi.

\(1 \le N \le 4*10^5\)

\(1 \le T_i \le 4*10^5\)

L ning maksimum qiymatini chop eting yoki buning imkoni bo'lmasa, 0 ni chop eting.