UCBINTC - Good

no tags 

 

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

You are given a sequence A consisting of N integers (not to be confused with the sequence from a previous

task). We will call the ith 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

The fi rst line of input contains the positive integer N (1 ≤ N ≤ 5000), the length of the se-

quence A. The second line of input contains N space separated integers representing the sequence

A (−100000 ≤ Ai ≤ 100000).

Output

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

Example

Input:
2
1 3

Output:
1
Input:
6
1 2 3 5 7 10

Output:
4
Input:
3
-1 2 0

Output:
1


Added by:Gabriel Menacho
Date:2014-09-09
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:2013年每周一赛第十四场, http://soj.me/9563