더블 청크

면접 대비

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

요약

N개 조각의 값을 연속된 덩어리로 나누어, 두 조각짜리 덩어리의 합이 모두 같게 만들 때 그런 덩어리의 최대 개수를 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 해시맵
정답자: 아직 제출이 없습니다

문제

초콜릿 바는 $N$ 개의 청크로 이루어져 있고, 번호는 1부터 $N$ 까지이다. $i$ 번 청크에는 땅콩 비트가 $A_i$ 개 들어 있다. 초콜릿 바를 여러 조각으로 나눌 수 있으며, 각 조각은 연속된 청크 한 개 이상으로 구성된다. 각 청크는 한 조각에만 속할 수 있다. 조각의 땅콩 비트 수는 그 조각에 속한 청크들의 땅콩 비트 수를 모두 더한 값이다.

조각이 정확히 두 개의 청크로 이루어졌을 때에만 그 조각을 더블 청크라고 한다. 모든 더블 청크의 땅콩 비트 합이 같아야 하므로, 이 조건을 지키면서 만들 수 있는 더블 청크의 최대 개수를 구하라.

입력

첫째 줄에 정수 $N$ ( $2 ≤ N ≤ 100000$ )이 주어진다.

둘째 줄에 $N$ 개의 정수 $A_i$ ( $1 ≤ A_i ≤ 10^9$ )가 주어진다.

출력

조건을 만족하면서 얻을 수 있는 더블 청크의 최대 개수를 정수 하나로 출력한다.

예제3

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