Cho dãy $A$ $=$ $(a_1,a_2,a_3,\dots ,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,\dots ,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\mathrm{\%}$ số điểm): $N\le 50$.
• Subtask $2$ ($30\mathrm{\%}$ số điểm): $N\le 500$.
• Subtask $3$ ($30\mathrm{\%}$ 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)