Good Numbers

Interview

Time limit1sMemory limit128 MB

Summary

Count the elements A_i that equal the sum of three elements appearing earlier in the sequence, where the same earlier element may be reused.

Level: Medium5 of 10
Topics: Hash map, Brute force, Array, Implementation
Solved: No attempts yet

Problem

You are given a sequence $A = A_1, A_2, \dots, A_N$ of $N$ integers.

The $i$ -th number $A_i$ is called a good number if it equals the sum of three numbers chosen from those that appear before it ( $A_1, \dots, A_{i-1}$ ). The same number may be chosen more than once. In other words, $A_i$ is good if there exist positions $j, k, l$ with $1 \le j, k, l \le i-1$ (not necessarily distinct) such that $A_i = A_j + A_k + A_l$ .

Given the sequence, count how many of its numbers are good numbers.

Input

The first line contains the size $N$ of the sequence $A$ . ( $1 \le N \le 5000$ )

The second line contains the elements of $A$ , separated by spaces. ( $-100{,}000 \le A_i \le 100{,}000$ )

Output

Print the number of good numbers on the first line.

Examples3

Example 1
Input
```
2
1 3
```
Expected output
```
1
```
Example 2
Input
```
6
1 2 3 5 7 10
```
Expected output
```
4
```
Example 3
Input
```
3
-1 2 0
```
Expected output
```
1
```