Cậu bé Askhat của chúng ta đã nhận thấy một hiện tượng thú vị — việc cố gắng bao phủ một mảng bằng các "bước nhảy" với tổng ngày càng lớn có thể không đơn giản như vẻ ngoài của nó. Tất nhiên, bây giờ bạn cần tìm cách để thực hiện điều đó.

Bạn được cho một dãy gồm $N$ số nguyên dương.

Hãy chia dãy đã cho thành số lượng đoạn tối đa sao cho:

1. Mỗi phần tử của dãy thuộc về đúng một đoạn.
2. Tổng các số trong mỗi đoạn, ngoại trừ đoạn đầu tiên, không nhỏ hơn tổng của đoạn trước đó.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa số nguyên $N$ ($1 \le N \le 5 \cdot 10^5$). Dòng tiếp theo chứa $N$ số nguyên dương $a_i$ ($1 \le a_i \le 10^9$), được phân tách bằng dấu cách.

Dữ liệu ra

In ra một số nguyên duy nhất — số lượng đoạn tối đa mà dãy đã cho có thể được chia thành.

Nhiệm vụ con

Bài toán này bao gồm năm nhiệm vụ con, với các ràng buộc bổ sung:

1. $1 \le N \le 20$, $a_i \le 10^6$. Được 13 điểm.
2. $1 \le N \le 500$. Được 14 điểm.
3. $1 \le N \le 3000$. Được 10 điểm.
4. $1 \le N \le 10^5$. Được 36 điểm.
5. Các ràng buộc gốc. Được 27 điểm.

Ví dụ

Dữ liệu vào 1

4
2 3 1 7

Dữ liệu ra 1

3

Dữ liệu vào 2

5
6 2 3 9 13

Dữ liệu ra 2

3

Dữ liệu vào 3

3
3 1 2

Dữ liệu ra 3

2