One day, Lucas is lining up to buy lunch at campus centre when he notices his friend Parsa right behind him. Lucas realizes that instead of waiting and ordering separately, it would be much faster for one of them to place a combined order for both, saving time on the transaction.

Other students in the line notice their strategy, and the idea quickly catches on. The following week, Lucas returns to the food court and sees a new trend: people are merging their orders! Specifically, a person can take on the order of the person immediately in front of or behind them, provided their own current combined order size is greater than or equal to the order size of that adjacent person. Once merged, the person whose order was taken leaves the line.

Watching this unfold, Lucas wonders: given the number of items each person in the line initially intends to order, how many different people could theoretically end up placing the single, final order for the entire line?

More formally, given an array ~A~ of ~n~ positive integers, where ~A_i~ is the number of items the ~i^{th}~ person in the line initially is ordering, how many distinct people can end up being the final person ordering, if a person who is responsible for ordering items ~\{A_b, \ldots, A_c\}~, ~1 \le b \le c \le n~ can merge their order with:

• the person responsible for ordering items ~\{A_a, \ldots, A_{b-1}\}~, ~1 \le a < b~ if ~\sum_{i=a}^{b-1} A_i \le \sum_{i=b}^{c} A_i~
• the person responsible for ordering items ~\{A_{c+1}, \ldots, A_{d}\}~, ~c < d \le n~ if ~\sum_{i=b}^{c} A_i \ge \sum_{i=c+1}^{d} A_i~

Input

The first line contains an integer ~n~, the number of people initially in the line.

The second line contains ~n~ integers: ~a_1, a_2, \ldots, a_n~.

Output

The number of different people who can end up ordering for the whole line.

Constraints

• ~1 \le n \le 10^6~
• ~1 \le a_i \le 10^6~

Example 1

Input

5
1 1 2 1 6

Output

1

Explanation

Only person ~5~ can end up ordering for the whole line.

Example 2

Input

5
3 1 3 3 2

Output

3

Explanation

People ~1, 3, 4~ can end up ordering for the whole line.

Example 3

Input

10
1 5 5 2 4 1 4 1 2 3

Output

6

Explanation

People ~2, 3, 5, 7, 9, 10~ can end up ordering for the whole line.