Muallif: __thecrash__ eb2e84947466

H. Sehrli gulzor

Vaqt limiti: 1000 ms Xotira limiti: 512 mb

Sehrgar shogirdi Nodira ustozining gulzoriga qarashi kerak. Gulzorda bir qatorga \(n\) ta gul ekilgan, \(i\)-gulning sehr kuchi \(a_i\) ga teng. Sehr kuchi musbat ham, manfiy ham, nol ham bo'lishi mumkin.

Ustoz ketishdan oldin shunday tayinladi: "Men qaytgunimcha barcha gullar tinchlansin, ya'ni har bir gulning sehr kuchi qat'iy manfiy bo'lsin."

Nodira faqat bitta afsunni biladi, va uning g'alati xususiyati bor. Afsun har doim gulzordagi eng kuchli bo'lakka tushadi:

1. Avval ketma-ket turgan gullardan iborat shunday \([l, r]\) bo'lak (\(1 \le l \le r \le n\)) tanlanadi, uning yig'indisi \(a_l + a_{l+1} + \ldots + a_r\) gulzordagi barcha bo'laklar yig'indilari ichida eng kattasi bo'lsin. Bunday bo'laklar bir nechta bo'lsa, Nodira ulardan istalganini tanlashi mumkin;
2. So'ng shu bo'lakdagi har bir gulning sehr kuchi \(1\) ga kamayadi.

Nodira barcha gullarni tinchlantirish uchun eng kamida necha marta afsun o'qishi kerak?

Kiruvchi ma'lumotlar

Birinchi qatorda bitta butun son \(n\) (\(1 \le n \le 5 \cdot 10^5\)) — gullar soni.

Ikkinchi qatorda \(n\) ta butun son \(a_1, a_2, \ldots, a_n\) (\(-10^6 \le a_i \le 10^6\)) — gullarning sehr kuchlari.

Chiquvchi ma'lumotlar

Bitta butun son — afsunlarning eng kam soni.

Misollar

1

4
3 -1 2 1

6

2

4
-3 -1 -4 -2

0

3

7
5 1000000 -300000 999999 -7 450000 0

1875005

Izoh

Birinchi misolda afsunlarni bunday o'qish mumkin:

1. \([3, -1, 2, 1]\): eng katta yig'indi \(5\), u \([1, 4]\) bo'lakda → \([2, -2, 1, 0]\);
2. eng katta yig'indi \(2\), bo'lak \([1, 1]\) → \([1, -2, 1, 0]\);
3. eng katta yig'indi \(1\), bo'lak \([1, 1]\) → \([0, -2, 1, 0]\);
4. eng katta yig'indi \(1\), bo'lak \([3, 3]\) → \([0, -2, 0, 0]\);
5. eng katta yig'indi \(0\), bo'lak \([1, 1]\) → \([-1, -2, 0, 0]\);
6. eng katta yig'indi \(0\), bo'lak \([3, 4]\) → \([-1, -2, -1, -1]\).