printРабочее место участника


1948. Good elements

Ограничения: время – 1s/2s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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\ ≤\ A_i\ ≤\ 100\ 000`).
The first and only line of output must contain the number of good elements in the sequence.

Sample Input #1

1 3

Sample Output #1


Sample Input #2

1 2 3 5 7 10

Sample Output #2


Sample Input #3

-1 2 0

Sample Output #3

Source: COCI 2012/2013, contest #6