Masala #WXGF6BL5EL

Xotira 64 MB Vaqt 1000 ms

Musiqaxo'r

Bitlandiyada musiqani ko'p eshitadiganlarni musiqaxo'r deb atashadi. Roboboy ham o'zini musiqaxo'r deb hisoblaydi. Uni telefonida N ta qo'shiqlar ketma-ketligi mavjud. Muammo shundaki biror qo'shiqni qo'ysa unda qo'shiqni o'tkazib yuborish yoki orqaga qaytish funksiyasi yo'q. U faqat turli qo'shiqlar eshitganda mazza qiladi va shu sababli biror eshitgan qo'shiq kelsa darrov telefonni o'chiradi. U biror qo'shiqni qo'yadi va eng ko'pi bilan nechta turli qo'shiq eshitishi mumkinligini toping.

Kiruvchi ma'lumotlar:

Kirish faylidan birinchi qatorda N(1≤N≤2⋅10⁵) Roboboyning qo'shiqlar soni.

Keyingi qatorda N ta qo'shiqlar. Bunda ular natural sonlar bilan ifodalanadi va milliarddan oshmaydi.

Chiquvchi ma'lumotlar:

Chiqish faylida yagona natural son Roboboy eshitishi mumkin bo'lgan maksimal qo'shiqlar soni.

Misollar

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

Izoh:

1-testda:

Agar 1-da turgan qo'shiqdan eshitishni boshlasa:

Faqatgina 1- va 2- qo'shiqlarni eshita oladi.

Agar 2-da turgan qo'shiqdan eshitishni boshlasa:

2 1 3 qo'shiqlarini eshita oladi.

Agar 3-da turgan qo'shiqdan boshlasa:

1 3,2,7,4 qo'shiqlarni eshita oladi.

Ko'rishimiz mumkinki bu u eshitishi mumkin bo'lgan eng ko'p qo'shiqlar soni.

2-testda har qanaqasiga faqat 1 ta qo'shiq eshitishi mumkin.