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

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 ≤ A_i ≤ 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