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

وزیر شهر شکرستان می‌خواهد از $n$ نفر از اشراف، زمین کشاورزی بخرد و آن را به مردم بفروشد. همه‌ی زمین ها به شکل یک مربع $1 \times 1$ و کنار هم، در یک ردیف قرار دارند. هر یک از این اشراف برای زمین خودش یک قیمت به وزیر اعلام کرده است. اکنون وزیر می‌خواهد این $n$ زمین را از اشراف خریداری کند و به روش زیر تقسیم کرده و به مردم بدهد.

1. زمین‌ها را به تعدادی بازه پشت سر هم افراز کند به طوری که مساحت زمین های همه بازه با هم برابر باشند.
2. مجموع قیمت‌ زمین های همه بازه ها با هم برابر باشند.
3. تعداد بازه ها بیشینه باشد.

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

ورودی

در خط اول ورودی یک عدد صحیح $n$ که برابر تعداد زمین ها است داده می شود. در خط بعدی $n$ عدد صحیح داده می شود که عدد $i$ام برابر $a_{i}$ است که همان قیمتی است که اشراف برای زمین $i$ام اعلام کردند. $$1 \leq n \leq 1\ 000\ 000$$ $$1 \leq a_{i} \leq 1\ 000\ 000\ 000$$

خروجی

در یک خط خروجی بیشینه تعداد بازه ها را چاپ کنید.

مثال

ورودی نمونه ۱

8
3 12 2 13 2 13 6 9 

خروجی نمونه ۱

4

توضیح نمونه ۱

می‌توان این ۸ زمین را به ۴ بازه به مساحت ۲ افراز کرد بطوری که مجموع قیمت زمین‌های داخل هریک از ۴ بازه برابر ۱۵ شود:

{3, 12}, {2, 13}, {2, 13}, {6, 9}

ورودی نمونه ۲

4
1 1 1 1 

خروجی نمونه ۲

4