Masala #0792

Xotira 16 MB Vaqt 1000 ms
14

Xilma xil konfetlar 🍬

O'tkir xilma-xil konfet yeyishni juda yaxshi ko'radi. Ammo unga konfetlarni hammasini yeyishi mumkin emas. O'tkir ko'pi bilan necha xil konfet yeyishi mumkinligini topishga yordam bering! Bizga \(N\) konfetdan iborat \(arr[]\) massivi berilgan, bu yerda \(N\) juft son va \(arr[i]\) konfet turi. Muammo shundaki, agar ulardan faqat \(N/2\) tasini yeyish mumkin bo'lsa, O'tkir yeyishi mumkin bo'lgan har xil turdagi konfetlarning maksimal sonini topishdir.


Kiruvchi ma'lumotlar:

Birinchi qatorda \(N\) butun juft son – massiv uzunligi beriladi \((1 ≤ N ≤ 2*10^5)\)

Ikkinchi qatorda sizga \(N\) ta son – massiv elementlari beriladi. Massiv elementlari 1018 dan oshmaydi.


Chiquvchi ma'lumotlar:

Chiqish faylida yagona butun son O'tkir yeyishi mumkin bo'lgan har xil turdagi konfetlarning maksimal sonini chop eting.


Misollar
# input.txt output.txt
1
8
4 4 5 5 6 6 7 7
4
2
4
2 2 3 1
2