Вам дано масив з цілих чисел . Ви його кладете в магічний мішечок. Можна робити наступну операцію довільну (можливо, нульову) кількість разів:
дістати непустий масив з мішечка;
вибрати довільний елемент масиву b_i;
видалити b_i, розділяючи масив на два (можливо, пустих) масиви;
покласти два нових масиви в мішечок.
Знайдіть мінімальну кількість операцій, яку слід застосувати, щоб у кінці в кожному масиві з мішечка кожен відрізок довжини більший ніж мав невід'ємну суму.
Перший рядок містить одне ціле число (1 \le n \le 10^5) — довжина масиву .
Другий рядок містить цілих чисел a_i (-10^6 \le a_i \le 10^6) — опис масиву .
Виведіть одне ціле число — мінімальну кількість операцій, яку слід застосувати, щоб у кінці в кожному масиві з мішечка кожен відрізок довжини більший ніж мав невід'ємну суму.
Приклад 1
Приклад 2
У першому прикладі можна, наприклад, видалити число , і тоді буде два масиви та . Зверніть увагу, що розбити на масив можна, бо ми не враховуємо відрізки довжиною .
У другому прикладі не потрібно нічого видаляти, масив уже задовольняє умовам.
У цій задачі кожен блок оцінюється потестово.
( балів): n \leq 10;
( балів): n \leq 100;
( балів): n \leq 2\,000;
( балів): без додаткових обмежень.