Cho dãy ~A~ ~=~ ~(a_1, a_2, a_3, …, a_N)~ các số nguyên không âm. Vị trí ~(1 \le i \le N)~ được gọi là một vị trí tốt nếu như ~a_i~ bằng tổng của ~ba~ giá trị xuất hiện ở các vị trí nhỏ hơn ~i~ (mỗi giá trị có thể tham gia vào việc tính tổng nhiều lần).

Yêu cầu

Hãy đếm xem trong dãy A có bao nhiêu vị trí tốt?

Input

Cho trong file văn bản GPOS.INP có cấu trúc như sau:

• Dòng đầu tiên chứa số nguyên dương ~N~ ~(1 \le N \le 5000)~,
• Dòng thứ hai chứa ~N~ số nguyên không âm ~a_1, a_2, a_3, …, a_N~.~(0 \le a_i \le 10^5)~.

Output

Ghi ra file văn bản GPOS.OUT theo cấu trúc như sau:

• Một dòng duy nhất là yêu cầu của bài toán

Scoring

• Subtask ~1~ (~40\%~ số điểm): ~N\le 50~.
• Subtask ~2~ (~30\%~ số điểm): ~N\le 500~.
• Subtask ~3~ (~30\%~ số điểm): ~N\le 5000~

Ví dụ

Input

2
1 3

Output

1

Input

6
1 2 3 5 7 10

Output

4

Giải thích ví dụ

• Ví dụ 1: vị trí ~2~ là vị trí tốt vì ~a_2~ ~=~ ~a_1~ + ~a_1~ + ~a_1~ (mỗi giá trị có thể tham gia vào việc tính tổng nhiều lần)