세 구간의 페이스

문제

마라톤 대회 운영진은 참가자에게 나누어 줄 페이스 안내표를 만들고 있다. 이번 코스는 출발점부터 결승점까지 순서대로 N개의 구간으로 나뉜다. 각 구간의 길이는 양의 정수이며, 안내표에는 이 구간들을 다시 세 개의 큰 구역으로 묶어 표시하려 한다. 구간의 순서를 바꾸거나 한 구간을 더 작게 나누는 일은 허용하지 않는다. 운영진은 서로 다른 두 경계를 골라 안내 표식을 설치한다. 첫 표식을 i번 구간 바로 뒤에, 두 번째 표식을 j번 구간 바로 뒤에 설치하면 첫 구역은 1번부터 i번 구간까지, 두 번째 구역은 i+1번부터 j번 구간까지, 세 번째 구역은 j+1번부터 N번 구간까지다. 세 구역에는 각각 적어도 한 구간이 들어가야 하므로 1 ≤ i < j ≤ N-1이어야 한다. 표식은 구간 사이에만 설치할 수 있으며, 출발점이나 결승점에는 설치할 수 없다. 운영진은 참가자가 세 구역을 비슷한 거리로 느끼기를 바란다. 이를 위해 각 구역에 속한 구간 길이를 모두 더해 구역의 길이를 구하고, 세 길이 중 최댓값에서 최솟값을 뺀 값을 거리 차이라고 정의한다. 이 값은 항상 0 이상의 정수다. 구역마다 포함된 구간의 개수는 달라도 되며, 비교하는 것은 오직 길이의 합이다. 가능한 모든 표식 배치 중 거리 차이가 가장 작은 배치를 찾아야 한다. 거리 차이가 같은 배치가 여러 개라면 첫 표식의 위치 i가 가장 작은 배치를 선택한다. i까지 같다면 두 번째 표식의 위치 j가 가장 작은 배치를 선택한다. 입력에서는 N이 3 이상이므로 가능한 배치는 항상 존재한다. 선택한 두 경계의 번호와 그때의 거리 차이를 구하는 프로그램을 작성한다.

입력

첫째 줄에 구간 수 N이 주어진다. 둘째 줄에 구간 길이 d_1, d_2, ..., d_N이 순서대로 공백으로 구분되어 주어진다.
모든 입력값은 정수이며 3 ≤ N ≤ 500, 1 ≤ d_i ≤ 1,000,000이다.

출력

선택한 첫 경계 i, 두 번째 경계 j, 거리 차이를 이 순서대로 한 줄에 공백으로 구분하여 출력한다. 동점이면 i가 작은 배치를, i도 같으면 j가 작은 배치를 출력한다.

5
2 3 4 1 5

2 4 0

4
1 1 1 1

1 2 1

3
8 2 5

1 2 6

출처: Devin.KR 자체 제작