You are given a sequence $A$ consisting of $N$ integers. We will call the $i^{\text{th}}$ sequence element good if it equals the sum of some three elements in positions strictly smaller than $i$ (an element can be used more than once in the sum).

How many good elements does the sequence contain?

Input Specification

The first line of input contains the positive integer $N$ $(1\le N\le 5000)$, the length of the sequence $A$.

The second line of input contains $N$ space-separated integers representing the sequence $A$ $(-100000\le A_i\le 100000)$.

Output Specification

The first and only line of output must contain the number of good elements in the sequence.

Scoring

In test data worth at least $40\mathrm{\%}$ of total points, $N\le 50$.

In test data worth at least $70\mathrm{\%}$ of total points, $N\le 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