Masala C

Robolandiya Sport Dasturlash federatsiyasi yangi turdagi musobaqa tashkil etmoqda. Musobaqaning hayratlanarli tarafi masalalar o'quvchilarning bilimidan kelib chiqib tuzilgan, aniqroq aytganda har bir ishtirokchi aynan $a_i$ masalani ishlay oladi va boshqa hech qaysi ishtirokchi u ishlay oladigan masalani ishlay olmaydi. Ushbu musobaqa 2 ta ishtirokchidan iborat guruhlar orasida bo'lib o'tadi. Quvonarlisi, hozirda ro'yxatdan o'tgan ishtirokchilar soni juft, ya'ni istalgan ishtirokchi musobaqada qatnasha oladi. Musobaqa jarayonida juda past natija ko'rsatgan jamoalar federatsiya obro'siga zarar yetkazishi mumkin. Shu sababdan federatsiya ishtirokchilarni o'zlari guruhlab chiqishga qaror qildi. Shunda har bir jamoa eng kamida $X$ ta masala ishlaydi. Siz shu $X$ ning eng katta qiymatini toping.

Birinchi qatorda bitta butun juft son $N \ (2 \le N \le 10^6)$ - ishtirokchilar soni kiritiladi.

Keyingi qatorda $N$ ta butun son $a_i \ (1 \le a_i \le 10^9)$ - har bir ishtirokchi ishlay oladigan masalalar soni beriladi.

Har bir jamoa ishlagan masalalar soni kamida $X$ bo'lishi mumkin bo'lgan maksimal qiymatni chop eting.