Uzb Eng

C16E. Merlin
: 2 c
: 64

Bir kuni ozining Minorasiga kelib Merlin shuni bilib qoldiki Margana uning hamma zakovat eliksiri bilan toldirilgan idishlarini sehrlab qoyganligini bilib qoldi. Merlin bu sehrni qanday yoqotishni biladi. Ammo sehrni yoqotish shuni talab qiladiki hamma qollanilayotgan idishlarda teng miqdorda eliksir bolishi zarur. Buni amalga oshirish uchun Merlin quyidagicha yol tutdi. U bir qancha idishlarni oladi va qolgan idishlarga soladi. U eliksirlarni ixtiyoriy tarzda qolgan idishlarga taqsimlashi mumkin. Bir qancha olingan idishlarni hammasini quyib bolganidan song bu idishlarni sindirib tashlaydi(Ulardan joduni yoqotib bolmaydi), va ularni tashlab yuboradi va qolgan idishlarda joduni yoqotishni amalga oshiradi. Sehrgarga minimal idishlarni sindirgan holda Margananing jodusini yoq qilishga yordam bering.

:
Birinchi satrda n raqami(2 <= n <= 105) - idishlar soni. Ikkinchi satrda n ta butun son, a1, a2, ... , an (1 <= ai <= 109) har bir idishdagi zakovat eliksirining miqdori.

:
Yagona qatorda Merlinning sindirishga majbur bolgan minimal idishlarning sonini chiqaring

3
2 3 2
4
4 4 4 4
5
1 2 3 4 5
1


0


2
:
:


Design by TUIT © 2012-2017 TUIT Online Judge. All rights reserved.