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~ ~(-100\,000 \le A_i \le 100\,000)~.

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\%~ of total points, ~N \le 50~.

In test data worth at least ~70\%~ 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