용액 2

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

요약

연속한 구간의 합 중 절댓값이 가장 작은 것을 찾아 그 값과 구간의 양 끝을 출력한다.

난이도: 보통10점 중 6점
유형: 누적 합, 정렬, 이분 탐색, 배열
정답자: 아직 제출이 없습니다

문제

중앙대학교에 숨겨진 화학연구소에는 산성과 염기성을 띠는 용액 $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
```