좋은 수

면접 대비

시간 제한1초메모리 제한128 MB

요약

수열에서 자기 앞에 있는 세 수의 합으로 표현되는 원소가 몇 개인지 센다. 같은 원소를 여러 번 골라도 된다.

난이도: 보통10점 중 5점
유형: 해시맵, 완전 탐색, 배열, 구현
정답자: 아직 제출이 없습니다

문제

정수 $N$ 개로 이루어진 수열 $A = A_1, A_2, \dots, A_N$ 이 있다.

수열의 $i$ 번째 수 $A_i$ 가, 자신보다 앞에 있는 수( $A_1, \dots, A_{i-1}$ ) 중에서 세 개를 골라 더한 값과 같으면 그 수를 좋은 수라고 한다. 이때 같은 수를 여러 번 골라도 된다. 즉, $A_i = A_j + A_k + A_l$ 을 만족하는 위치 $j, k, l$ ( $1 \le j, k, l \le i-1$ , 서로 같아도 된다)이 존재하면 $A_i$ 는 좋은 수이다.

수열이 주어졌을 때, 좋은 수가 모두 몇 개인지 구하여라.

입력

첫째 줄에 수열 $A$ 의 크기 $N$ 이 주어진다. ( $1 \le N \le 5000$ )

둘째 줄에 수열 $A$ 의 각 원소가 공백으로 구분되어 주어진다. ( $-100{,}000 \le A_i \le 100{,}000$ )

출력

첫째 줄에 좋은 수의 개수를 출력한다.

예제3

예제 1
입력
```
2
1 3
```
예상 출력
```
1
```
예제 2
입력
```
6
1 2 3 5 7 10
```
예상 출력
```
4
```
예제 3
입력
```
3
-1 2 0
```
예상 출력
```
1
```