함께 옮길 두 상자

문제

택배 작업장에는 배송 상자 N개가 한 줄로 놓여 있다. 상자에는 왼쪽부터 1번부터 N번까지 번호가 붙어 있으며, 각 상자의 무게는 양의 정수로 기록되어 있다. 작업자는 기록된 무게를 이용하여 이번 작업에서 함께 옮길 상자 두 개를 고르려고 한다. 작업장의 운반 도구는 줄에서 바로 이웃한 상자 두 개만 한 번에 집을 수 있다. 따라서 i번 상자와 i+1번 상자는 함께 고를 수 있지만, 사이에 다른 상자가 있는 두 상자는 함께 고를 수 없다. 맨 왼쪽 상자와 맨 오른쪽 상자도 실제로 이웃해 있을 때만 함께 고를 수 있다. 상자의 순서를 바꾸거나 상자를 줄에서 미리 빼내는 일은 허용되지 않는다. 작업자는 한 번에 처리하는 무게를 크게 하려고 한다. 함께 고를 수 있는 모든 두 상자 중 무게의 합이 가장 큰 두 상자를 선택한다. 무게의 합이 가장 큰 선택이 여러 개라면, 두 상자 중 왼쪽 상자의 번호가 가장 작은 선택을 사용한다. 무게가 같은 상자라도 번호가 다르면 서로 다른 상자로 취급한다. 예를 들어 어떤 선택의 왼쪽 상자 번호가 3이라면, 그 선택은 정확히 3번 상자와 4번 상자를 뜻한다. 출력할 번호는 두 상자의 번호를 이어 붙인 값이나 오른쪽 상자의 번호가 아니라, 이 왼쪽 상자의 번호다. 여러 번 운반한 결과를 계산하는 것이 아니라 처음 놓인 줄에서 한 번의 선택만 결정하면 된다. 상자가 하나뿐이면 두 개를 고를 수 없다. 이 경우에는 선택한 상자의 번호와 무게의 합을 모두 0으로 정한다. 상자가 두 개 이상인 경우에는 무게 제한 없이 반드시 두 상자를 선택한다. 상자의 무게 목록이 주어질 때, 선택한 두 상자 중 왼쪽 상자의 번호와 두 상자 무게의 합을 구하는 프로그램을 작성한다.

입력

첫째 줄에 상자의 수 N이 주어진다. N은 1 이상 1,000 이하의 정수다.
둘째 줄에 1번부터 N번까지 상자의 무게 W_i가 순서대로 공백으로 구분되어 주어진다. 각 W_i는 1 이상 1,000 이하의 정수다.

출력

선택한 두 상자 중 왼쪽 상자의 번호와 두 상자 무게의 합을 공백으로 구분하여 한 줄에 출력한다. 최대 합을 만드는 선택이 여러 개면 왼쪽 상자의 번호가 가장 작은 것을 출력한다. N이 1이면 0 0을 출력한다.

6
4 9 3 10 2 5

1 13

1
17

0 0

4
2 3 8 6

3 14

출처: Devin.KR 자체 제작