나란한 두 객실의 준비 시간

문제

한 호텔의 복도에는 객실 N개가 한 줄로 놓여 있다. 객실에는 복도 입구에서 가까운 순서대로 1번부터 N번까지 번호가 붙어 있다. 호텔 직원은 각 객실을 손님에게 내주기 전에 필요한 준비 시간을 조사해 배열에 적었다. i번 객실의 준비 시간은 A_i분이다. 이미 준비를 마친 객실의 준비 시간은 0분일 수 있다. 오늘은 함께 도착하는 두 손님에게 나란히 붙어 있는 객실 두 개를 배정하려고 한다. 배정할 수 있는 객실 쌍은 번호가 i와 i+1인 두 객실뿐이다. 따라서 1번과 N번 객실은 N이 2인 경우를 제외하면 서로 붙어 있는 객실로 취급하지 않는다. 다른 객실을 사이에 둔 두 객실을 선택하거나, 같은 객실을 두 번 선택할 수는 없다. 직원 한 명이 선택한 두 객실을 차례로 준비하므로, 두 객실을 모두 준비하는 데 걸리는 시간은 두 준비 시간의 합이다. 객실 사이를 이동하는 데 걸리는 시간은 계산하지 않는다. 준비 순서를 바꾸어도 합은 달라지지 않으며, 선택하지 않은 객실의 준비 시간은 결과에 영향을 주지 않는다. 호텔은 두 객실의 준비 시간 합이 가장 작은 쌍을 선택한다. 가장 작은 합을 만드는 쌍이 여러 개라면, 두 객실 중 작은 객실 번호가 가장 작은 쌍을 선택한다. 예를 들어 2번과 3번 객실의 합과 5번과 6번 객실의 합이 같은 최솟값이라면 2번과 3번 객실을 선택한다. 모든 객실의 준비 시간이 같더라도 이 규칙을 그대로 적용한다. 객실은 적어도 두 개이므로 선택할 수 있는 쌍은 항상 존재한다. 주어진 준비 시간 배열을 보고 호텔이 선택할 두 객실 중 작은 객실 번호와, 그 두 객실의 준비 시간 합을 구하는 프로그램을 작성한다.

입력

첫째 줄에 객실 수를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 1,000)
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 구분되어 주어진다. (0 ≤ A_i ≤ 1,000)

출력

선택한 두 객실 중 작은 객실 번호와 두 객실의 준비 시간 합을 공백으로 구분하여 한 줄에 출력한다.

6
8 3 4 2 5 9

3 6

4
0 0 0 0

1 0

2
9 1

1 10

출처: Devin.KR 자체 제작