400548: GYM100203 G Good elements

Memory Limit:64 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Good elementstime limit per test1 secondmemory limit per test64 megabytesinputstandard inputoutputstandard output

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.

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

加入题单

上一题 下一题 算法标签: