Ділимо масив#509

Ділимо масив

0,5 секунди
256 мегабайтів
Складна

Вам дано масив з цілих чисел . Ви його кладете в магічний мішечок. Можна робити наступну операцію довільну (можливо, нульову) кількість разів:

  1. дістати непустий масив з мішечка;

  2. вибрати довільний елемент масиву b_i;

  3. видалити b_i, розділяючи масив на два (можливо, пустих) масиви;

  4. покласти два нових масиви в мішечок.

Знайдіть мінімальну кількість операцій, яку слід застосувати, щоб у кінці в кожному масиві з мішечка кожен відрізок довжини більший ніж мав невід'ємну суму.

Вхідні дані

Перший рядок містить одне ціле число (1 \le n \le 10^5) — довжина масиву .

Другий рядок містить цілих чисел a_i (-10^6 \le a_i \le 10^6) — опис масиву .

Вихідні дані

Виведіть одне ціле число — мінімальну кількість операцій, яку слід застосувати, щоб у кінці в кожному масиві з мішечка кожен відрізок довжини більший ніж мав невід'ємну суму.

Приклади

Приклад 1

Loading
Loading

Приклад 2

Loading
Loading

Примітка

У першому прикладі можна, наприклад, видалити число , і тоді буде два масиви та . Зверніть увагу, що розбити на масив можна, бо ми не враховуємо відрізки довжиною .

У другому прикладі не потрібно нічого видаляти, масив уже задовольняє умовам.

Оцінювання

У цій задачі кожен блок оцінюється потестово.

  1. ( балів): n \leq 10;

  2. ( балів): n \leq 100;

  3. ( балів): n \leq 2\,000;

  4. ( балів): без додаткових обмежень.