Наш маленький Асхат заметил интересное явление: попытка покрыть массив «прыжками» из всё возрастающих сумм может оказаться не такой простой, как кажется. Конечно, теперь вам нужно найти способ сделать это.

Дана последовательность положительных целых чисел длины $N$.

Разбейте данную последовательность на максимальное количество сегментов так, чтобы:

1. Каждый элемент последовательности принадлежал ровно одному сегменту.
2. Сумма чисел в каждом сегменте, кроме первого, была не меньше, чем в предыдущем.

Входные данные

Первая строка входных данных содержит целое число $N$ ($1 \le N \le 5 \cdot 10^5$). Следующая строка содержит $N$ положительных целых чисел $a_i$ ($1 \le a_i \le 10^9$), разделенных пробелами.

Выходные данные

Выведите единственное целое число — максимальное количество сегментов, на которое можно разбить данную последовательность.

Подзадачи

Эта задача содержит пять подзадач с дополнительными ограничениями:

1. $1 \le N \le 20$, $a_i \le 10^6$. Оценивается в 13 баллов.
2. $1 \le N \le 500$. Оценивается в 14 баллов.
3. $1 \le N \le 3000$. Оценивается в 10 баллов.
4. $1 \le N \le 10^5$. Оценивается в 36 баллов.
5. Исходные ограничения. Оценивается в 27 баллов.

Примеры

Входные данные 1

4
2 3 1 7

Выходные данные 1

3

Входные данные 2

5
6 2 3 9 13

Выходные данные 2

3

Входные данные 3

3
3 1 2

Выходные данные 3

2