Kuklite jagamine

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

요약

왼쪽에서 N1개, 오른쪽에서 N2개의 상자를 골라 두 사람이 가진 쿠키 수의 차이를 최소로 만든다.

난이도: 보통10점 중 6점
유형: 누적 합, 투 포인터, 배열
정답자: 아직 제출이 없습니다

문제

Laual seisavad reas $N$ karpi. Karbid on nummerdatud vasakult paremale $1 \ldots N$ . Karbis number $i$ on $K\_i$ vastlakuklit. Jüri ja Mari tahavad jagada karbid kaheks nii, et Jüri saaks $N\_1$ vasakpoolset ja $N\_2$ parempoolset karpi ning Mari kõik ülejäänud. Aita neil karbid jagada nii, et nad saaks võimalikult võrdselt kukleid!

입력

Tekstifaili esimesel real on karpide arv $N$ ( $1 \le N \le 100\\,000$ ). Järgmisel $N$ real on igaühel üks täisarv $K\_i$ : karbis number $i$ olevate kuklite arv ( $1 \le i \le N$ , $0 \le K\_i \le 10\\,000$ ).

출력

Tekstifaili ainsale reale väljastada kaks tühikuga eraldatud täisarvu $N\_1$ ja $N\_2$ , mis tähendavad, et kui Jürile anda $N\_1$ vasakpoolset ja $N\_2$ parempoolset karpi ning Marile kõik ülejäänud karbid, siis on nende saadud kuklite arvude vahe absoluutväärtus võimalikult väike. Kui võrdselt häid vastuseid on mitu, siis väljastada ükskõik milline neist.

예제2

예제 1
입력
```
3
1
2
1
```
예상 출력
```
1 1
```
예제 2
입력
```
5
2
2
1
2
2
```
예상 출력
```
1 1
```