Masala #1176

Xotira 16 MB Vaqt 1000 ms
14

Boltavoy va guruhlarga ajratish #2

Boltavoyni eslaysizmi? U bugun yana o'z o'quvchilarini guruhlarga ajratmoqchi. Uning o'quvchilari har xil davlatlardan kelgani uchun u guruhlarni quyidagicha ajratmoqchi.

  • Hech qaysi o'quvchi guruhsiz qolib ketmaslik kerak
  • Har bir guruhda 1 ta yoki 2 tadan o'quvchi bo'lishi kerak.
  • Bitta davlatdan bo'lgan o'quvchilar bir xil guruhga tushib qolmasin.

Boltavoy guruhlar sonini minimallashtirmoqchi. Uning yaqin do'sti sifatida unga yordam bering


Kiruvchi ma'lumotlar:

Kirish faylining birinchi qatorida N (1≤N≤\(10^5\)) - o'quvchilar soni

Keyingi qatorda N ta sondan tashkil topgan massiv \(a_1\),\(a_2\),…,\(a_N\)(1≤\(a_i\)\(10^5\)) - har bir o'quvchining qaysi davlatdan ekanligi.


Chiquvchi ma'lumotlar:

Chiqish faylining yagona qatorida bitta son - minimal guruhlar sonini chop eting.


Misollar
# input.txt output.txt
1
6
3 1 1 1 1 1
5
2
2
1 2
1
Izoh:

Boltavoy guruhlarga ajirata olishi kafolatlanadi.