Задача #1176

Память 16 MB Время 1000 ms Сложность 15 %

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

Входные данные:

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.

Выходные данные:

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

Примеры

#	input.txt	output.txt
1	6 3 1 1 1 1 1	5
2	2 1 2	1

Примечание:

Boltavoy guruhlarga ajirata olishi kafolatlanadi.

Telegram Facebook

Отправить решение

Пожалуйста, войдите в систему, чтобы выполнить это действие,если у вас нет учетной записи, вы можете зарегистрироваться в любое время