A1500.[COCI-2012_2013-contest6]#4 DOBRI

You are given a sequence A consisting of N integers (not to be confused with the sequence from the 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?

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 (-100 000 ≤
Ai ≤ 100 000).

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

In test data worth at least 40% of total points, N ≤ 50.
In test data worth at least 70% of total points, N ≤ 500.