C. Sahna chiroqlari

Litsey aktlar zali sahnasida 30 ta chiroq bor, ular 0 dan 29 gacha raqamlangan. j-chiroq yonib turganda 2ʲ vatt quvvat sarflaydi.

Chiroqlar N ta tugma bilan boshqariladi. i-tugma yoqilganda chiroqlarning ma’lum bir to‘plami yonadi; bu to‘plam bitta butun son aᵢ bilan beriladi: j-chiroq shu to‘plamda bo‘lishi uchun aᵢ ning ikkilik yozuvida j-bit 1 bo‘lishi kerak. Chiroq kamida bitta yoqilgan tugma uni yoqsa, yonadi (bir nechta tugma bitta chiroqni yoqsa ham, u bitta chiroq bo‘lib yonadi).

Hozir barcha N ta tugma yoqilgan. Tejash maqsadida sahna ustasi Sardor tugmalardan aniq bittasini o‘chirmoqchi. Qaysi tugmani o‘chirsa, sahna eng kam quvvat sarflaydi? Shu eng kam quvvatni toping.

Kirish ma’lumotlari

Birinchi qatorda bitta butun son N — tugmalar soni.

Ikkinchi qatorda N ta butun son a₁, a₂, …, a_N.

Chiqish ma’lumotlari

Bitta butun son — bitta tugma o‘chirilgandan keyingi eng kam quvvat (vattda).

Cheklovlar

• 2 ≤ N ≤ 2·10⁵
• 0 ≤ aᵢ < 2³⁰

1-misol: 5 = 0101₂, 2 = 0010₂, 8 = 1000₂, 1 = 0001₂ — hammasi yoqilganda 0–3-chiroqlar yonadi, 15 vatt. 8 ni o‘chirsak 0101₂ | 0010₂ | 0001₂ = 0111₂ = 7 vatt; 5 ni o‘chirsak — 11, 2 ni — 13, 1 ni — 15.

2-misol: eng katta son (4) ni o‘chirsak 3 | 4 = 7 vatt, 3 ni o‘chirsak esa faqat 4 vatt.