Masala #XLKQVLRVKM
Musobaqa
Huquqni muhofaza qilish organlaridagi kutilmagan muammolar Shohruhni yangi kasbni egallashga majbur qildi: u kompyuter fanlari bo‘yicha jamoaviy musobaqaning bosh tashkilotchisiga aylandi.
Musobaqada ishtirok etishni xohlovchi N ta klublar mavjud. Klublar prezidentlari juda o'jar va musobaqada jamoaning barcha klub a'zolari ishtirok etishi mumkin bo'lgan taqdirdagina qatnashadilar.
Tanlov ikki turdan iborat: saralash va final. Raqobat qilayotgan barcha jamoalar teng miqdordagi a'zolarga ega bo'lishi va bitta jamoaning barcha a'zolari bir klubga tegishli bo'lishi kerak. Saralash bosqichida har bir klubning istalgan sonidagi jamoalar ishtirok etishi mumkin va har bir klubning eng yaxshi jamoasi final bosqichiga yo‘llanma oladi.
Shohruh biladiki, unga reklama kerak. Shu sababli, u finalda tomoshabinlar soni imkon qadar ko'p bo'lishi uchun final ishtirokchilari sonini ko'paytirishni xohlaydi.
Yodda tuting, har bir ishtirokchi klub finalda bitta jamoa bilan chiqish huquqiga ega. Bundan tashqari, musobaqada kamida ikkita klub ishtirok etishi kerak, aks holda musobaqa homiylarni jalb qilish uchun juda zerikarli bo'ladi.
Finalda ishtirokchilarning maksimal sonini aniqlang, shunda Shohruh jamoa o'lchamini tanlashi shart bo'lmaydi.
Birinchi qatorda N - ishtirokchi jamoalar soni kiritiladi.
Keyingi qatorda N ta butun son - har bir klubdagi ishtirokchilar soni kiritiladi.
\(2 \le N \le 2 \times 10^5\)
\(1 \le A_i \le 2 \times 10^6\)
Finalda ishtirok etishi mumkin bo'lgan maksimum ishtirokchilar (jamoalar emas!) sonini chop eting.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
3 1 2 4 |
4 |
| 2 |
2 1 5 |
2 |
| 3 |
5 4 6 3 8 9 |
9 |
1-testda har bir jamoa 2 kishilik qilib tuziladi. 1-klub 2 kishilik jamoalarga bo'lina olmagani sabab qatnashmaydi. Qolgan ikki klubning har biridan bittadan jamoa finalga chiqsa umumiy jamoalar soni*jamoa o'lchami 2*2 = 4 kishi finalda qatnashadi.
Telegram kanalimizga obuna bo'ling