Double Chunks

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

요약

초콜릿 바를 여러 조각으로 나눌 때, 같은 합을 갖는 두 덩어리 조각을 최대 몇 개 만들 수 있는지 구한다.

난이도: 보통10점 중 6점
유형: 누적 합, 해시맵, 그리디
정답자: 아직 제출이 없습니다

문제

You have a chocolate bar consisting of $N$ chunks (numbered from $1$ to $N$ ). Chunk $i$ contains $A\_i$ peanut bits. You can divide the chocolate bar into several pieces, with each piece consisting of one or more consecutive chunks. Each chunk can only be part of one piece. The total number of peanut bits in a piece is simply the sum of the peanut bits from each of its chunks.

A piece is considered a double chunk if and only if it consists of exactly two chunks. You are required to divide the chocolate bar into as many double chunks as possible, all having the same total number of peanut bits. Determine the maximum number of double chunks you can get while satisfying this requirement.

입력

The first line consists of an integer $N$ ( $2 ≤ N ≤ 100\\, 000$ ).

The second line consists of $N$ integers $A\_i$ ( $1 ≤ A\_i ≤ 10^9$ ).

출력

Output a single integer representing the maximum number of double chunks you can get while satisfying the requirement.

예제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
```