Bạn được cấp một dãy ~A~ gồm ~N~ số nguyên (đừng nhầm với dãy ở nhiệm vụ trước). Chúng ta sẽ gọi phần tử thứ ~i~ của dãy là tốt nếu nó bằng tổng của một số phần tử ở các vị trí nhỏ hơn ~i~ (một phần tử có thể được sử dụng nhiều lần trong tổng).

Chuỗi chứa bao nhiêu phần tử tốt?

Input

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 5000)~, độ dài của dãy ~A~.
• Dòng thứ 2 chứa ~N~ số nguyên cách nhau bằng dấu cách biểu thị dãy ~A~ ~(-100 000 ≤ Ai ≤ 100 000)~.

Output

• Dòng đầu tiên và duy nhất của đầu ra phải chứa số phần tử tốt trong dãy.

Scoring

• Dữ liệu kiểm tra đạt ít nhất 40% tổng số điểm, ~N ≤ 50~.
• Trong phần thi có giá trị ít nhất 70% tổng số điểm, ~N ≤ 500~.

Sample Input 1

2
1 3

Sample Output 1

1

Sample Input 2

6
1 2 3 5 7 10

Sample Output 2

4

Sample Input 3

3
-1 2 0

Sample Output 3

1