UCBINTC - Good

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 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 (−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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.