Description

You are given a sequence A consisting of $N$ integers (not to be confused with the sequence from the previous task). We will call the $i^{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 Format

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

The second line of input contains $N$ space-separated integers representing the sequence A ($-100\,000 \leq A_i \leq 100\,000$).

Output Format

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

2
1 3

1

6
1 2 3 5 7 10

4

3
-1 2 0

1

Hint

In test data worth at least $40\%$ of total points, $N \leq 50$.

In test data worth at least $70\%$ of total points, $N \leq 500$.