Cho dãy gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Hãy chia dãy số này thành nhiều đoạn con liên tiếp nhất sao cho:

• Mỗi phần tử phải nằm trong đúng một đoạn.

• Tổng các phần tử trong mỗi đoạn con đều là số dương.

• Tổng các phần tử của đoạn con đứng trước không vượt quá tổng các phần tử của đoạn con đứng sau.

Cụ thể, tìm số nguyên ~k~ lớn nhất sao cho tồn tại các vị trí cắt ~0 = x_0 < x_1 < x_2 < \dots < x_{k-1} < x_k = n~ thỏa mãn điều kiện sau:

1. ~\displaystyle \sum_{j=x_{i-1}+1}^{x_i} a_j > 0 \quad \forall 1 \le i \le k~.

2. ~\displaystyle \sum_{j=x_{i-1}+1}^{x_i} a_j \le \sum_{j=x_i+1}^{x_{i+1}} a_j \quad \forall 1 \le i < k~.

Input

• Dòng đầu tiên chứa số nguyên ~n~ ~(1 \le n \le 10^5)~.

• Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(\sum a_i > 0, \sum |a_i| \le 10^5)~.

Output

• In ra một số nguyên duy nhất là số đoạn nhiều nhất chia được.

Scoring

Sample Input 1

6
2 -1 1 1 3 -1

Sample Output 1

4