G. Good elements
time limit per test
1 second
memory limit per test
64 megabytes
input
stdin
output
stdout

You are given a sequence A consisting of N integers. We will call the i-th 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

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

The second line of input contains N space-separated integers representing the sequence A ( - 105 ≤ Ai ≤ 105).

Output

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

Examples
Input
2
1 3
Output
1
Input
6
1 2 3 5 7 10
Output
4
Input
3
-1 2 0
Output
1