문제

정수 N개로 이루어진 수열 A가 주어진다. (이 수열은 이전 문제의 수열과는 다른 수열이다.)

수열의 i번째 원소 A[i]가, i보다 작은 위치에 있는 어떤 세 원소의 합과 같다면 A[i]를 좋은(good) 원소라고 하자.

같은 원소를 여러 번 사용하는 것도 허용된다.

수열에 좋은 원소가 몇 개 있는지 구하여라.

입력

첫째 줄에 수열의 길이 N이 주어진다. (1 ≤ N ≤ 5000)

둘째 줄에 수열 A의 원소 N개가 공백으로 구분되어 주어진다. (-100000 ≤ A[i] ≤ 100000)

출력

좋은 원소의 개수를 출력한다.

예제 입력 1

2
1 3

예제 출력 1

1

예제 입력 2

6
1 2 3 5 7 10

예제 출력 2

4

예제 입력 3

3
-1 2 0

예제 출력 3

1