Masala #SC5JUXTRQM

Extensions (uzaytirgichlar)

Nodir o’tgan o’quv yilida N ta olimpiadada qatnashdi va har birida bittadan uzaytirgich (pilot) yutib oldi. Bunda i uzaytirgichda a[i] ta rozetkasi bor.

Shuningdek, Nodirda cheksiz ko’p miqdorda telefonlar bor. Har bir telefonni quvvatlantirish uchun unga bittadan rozetka kerak, biroq Nodirning uyida energiya manbai bitta.

Uzaytirgichlarni bir-biriga shunday tartibda ulangki, bunda energiya manbalarini soni maksimal bo’lsin va iloji boricha ko’proq telefonni quvvatlantirsin.

Birinchi qatorda sizga N soni beriladi - jami uzaytirgichlar soni.

Ikkinchi qatorda a[1], a[2], ..., a[N] - uzaytirgichlar 

•  \(1 ≤ N ≤ 10^5\)

• \(2 ≤ a_i ≤100\), barcha \(1 ≤ i ≤ N\) uchun

  Subtasklar:
   1. (15 ball) \(N=1\)

   2. (20 ball) \(N ≤ 8\)

   3. (20 ball) \(a[1] = a[2] = ... = a[N]\)

   4. (45 ball) Qo'shimcha chegaralarsiz

Yagona qatorda ko’pi bilan nechta telefonni quvvatlantish mumkinligini chiqaring.