• محدودیت زمان: ۱ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

همانطور که از اسمش برمی‌آید، آقای خوش‌قلب به فکر همه است؛ حتی به فکر افراد معتاد. برای همین او از همه‌ی معتاد‌های سراسر کشور دعوت کرده که به پیش او بروند تا فکری به حالشان بکند.

اولین معتاد امروز به پیش آقای خوش‌قلب رفت. آقای خوش‌قلب ابتدا باید "سطح اعتیاد" این فرد را معین کند. برای این کار، از شخص معتاد یک تست گرفته شد. آقای خوش‌قلب تعداد خیلی زیادی جسم روی میز گذاشت و به معتاد گفت که اجسام یکسان را بشمرد و روی کاغذی بنویسد از هر جسم چندتا روی میز موجود است. آقای خوش‌قلب سطح اعتیاد افراد را بصورت عددی طبیعی مشخص می‌کند و می‌دانیم که یک معتاد با سطح اعتیاد kk، هر جسم روی میز را kkبار می‌بیند. (پس به ازای هر جسم موجود عددی که روی کاغذ می‌نویسد kk برابر تعداد واقعی است.)

حال آقای خوش‌قلب به خانه‌ی خود رفته و حین دیدن بازی‌های پرهیجان المپیک، می‌خواهد که سطح اعتیاد معتاد را بدست آورد. اما ناگهان متوجه می‌شود که یادش نمی‌آید چه تعداد از هر جسم روی میز بوده! با شتاب به سوی کیف خود رفته و برگه‌ی نوشته‌های معتاد را بیرون می آورد. او با تمام خوش‌قلبی خود، می‌خواهد بفهمد که حداقل چند جسم روی میز بوده است تا کمترین مقدار هزینه به مسئول چیدمان اجسام روی میز بدهد! (کمی خسیس هم هست)

حال خوش‌قلب به سراغ شما آمده و با دادن اعداد نوشته‌شده روی کاغذ معتاد به شما، از شما می‌خواهد که بگویید کمترین مقدار ممکن برای تعداد اجسام روی میز چه قدر میتوانسته باشد.

ورودی

در سطر ورودی یک عدد nn آمده است که نمایانگر تعداد اعداد روی کاغذ معتاد است. (که برابر تعداد اجسام مختلف روی میز است.)

سپس در سطر دوم ورودی nn عدد آمده است که با فاصله از هم جدا شده‌اند و نمایانگر اعداد نوشته شده روی کاغذ هستند. 1n1 000 000 1 \le n \le 1\ 000\ 000

اعداد روی کاغذ کوچکتر مساوی 1 000 000 0001\ 000\ 000\ 000 هستند.

خروجی

خروجی باید شامل یک عدد باشد که برابر کمترین تعداد اجسام ممکن روی میز است.

مثال

ورودی نمونه ۱

3
5 5 10
Plain text

خروجی نمونه ۱

4
Plain text

اگر سطح اعتیاد معتاد برابر ۵ باشد، می‌توان گفت روی میز ۴ جسم بوده‌ است که ۲ تای آن یک شکل بودند.

ورودی نمونه ۲

3
1 2 3
Plain text

خروجی نمونه ۲

6
Plain text

چون معتاد از یکی از اجسام تنها یک دانه دیده، سطح اعتیاد او تنها می‌تواند ۱ باشد پس همه‌ی اجسام گفته‌شده توسط معتاد روی میز موجود هستند؛ سه نوع جسم و از نوع اول یک دانه، از نوع دوم ۲ تا و از نوع سوم، ۳ تا.


ارسال پاسخ برای این سؤال
فایلی انتخاب نشده است.