용액 2

면접 대비

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

요약

N개의 정수가 주어질 때 합의 절댓값이 가장 작은 연속 구간을 찾아, 그 합과 구간의 양 끝 번호를 출력합니다.

난이도: 보통10점 중 4점
유형: 누적 합, 정렬
정답자: 아직 제출이 없습니다

문제

중앙대학교에 숨겨진 화학연구소에는 산성과 염기성을 띠는 용액 $N$ 개가 일렬로 나열되어 있다. 푸앙이는 특성값이 $0$ 보다 크면 산성, $0$ 보다 작으면 염기성이라고 생각한다. 또한 특성값의 절댓값이 작을수록 중성에 가깝다고 생각한다. $i$ 번 용액의 특성값은 $s_i$ 이다.

특성값이 $a$ , $b$ 인 두 용액을 섞으면 화학 반응에 의해 특성값이 $a + b$ 인 용액이 된다. 푸앙이는 나열된 $N$ 개의 용액 중 연속된 구간의 용액들을 섞어 중성에 가까운 용액을 만들고자 한다. 푸앙이가 만들 수 있는 가장 중성에 가까운 용액의 특성값과 그 용액을 만드는 방법을 구해 보자.

입력

첫 번째 줄에 양의 정수 $N$ 이 주어진다.

두 번째 줄에 정수 $s_1$ , $s_2$ , $s_3$ , $\cdots$ , $s_N$ 이 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 푸앙이가 만들 수 있는 가장 중성에 가까운 용액의 특성값을 출력한다.

두 번째 줄에 양의 정수 $L$ , $R$ 을 공백으로 구분하여 출력한다. $L$ 번부터 $R$ 번까지의 용액을 섞었다는 뜻이다.

가능한 경우가 여러 가지라면 그중 아무거나 하나를 출력한다.

제한

$1 \le N \le 1\,000\,000$
$-10^9 \le s_i \le 10^9$
$1 \le i \le N$
$1 \le L \le R \le N$

예제3

예제 1
입력
```
4
1 2 -1 -1
```
예상 출력
```
0
2 4
```
예제 2
입력
```
3
-8 2 3
```
예상 출력
```
2
2 2
```
예제 3
입력
```
5
1 -2 3 -2 1
```
예상 출력
```
0
2 5
```