셋 중 둘

Vasya는 최근 고객 흐름의 접수를 최적화하는 새로운 알고리즘을 개발했고, 다음 문제를 생각했다.

계산대의 대기열에 n명의 사람이 있고, 각 사람은 양의 정수 ai로 특징지어진다고 하자. 이는 해당 고객을 응대하는 데 필요한 시간이다. 이 계산대의 특별한 점은 두 고객을 동시에 응대할 수 있다는 것이다. 그러나 두 고객을 응대하는 데 각각 ai와 aj의 시간이 필요하다면, 두 고객 모두를 응대하는 데 필요한 시간은 max(ai, aj)와 같다. 고객 응대는 중단할 수 없는 과정이라는 점에 유의하라. 따라서 두 사람이 동시에 계산대로 오면 동시에 응대를 받기 시작하고 동시에 끝난다(둘 중 한 명은 기다려야 할 수도 있다).

Vasya는 자신의 알고리즘에 기발한 휴리스틱을 사용했다. 대기열에 기다리는 사람이 한 명보다 많은 동안에는 대기열 맨 앞의 세 사람 중 임의의 두 사람을 동시에 보낸다. 대기열에 고객 번호 i인 한 명만 남았다면, 그 고객은 계산대로 가서 ai의 시간 동안 응대를 받는다. 고객 응대 단계의 총횟수는 항상 ⌈n / 2⌉와 같다는 점에 유의하라.

Vasya는 이 방법이 우리 모두가 싫어하는 대기열을 처리하는 데 도움이 될 것이라고 생각한다. 그래서 그는 이 알고리즘을 사용할 때 전체 대기열을 모두 응대하는 데 필요한 최소 시간을 구하는 프로그램을 작성해 달라고 요청했다.

입력 파일의 첫 번째 줄에는 수열에 있는 사람 수를 나타내는 하나의 수 n (1 ≤ n ≤ 1000)이 주어진다. 두 번째 줄에는 공백으로 구분된 정수 a1, a2, ..., an (1 ≤ ai ≤ 106)이 주어진다. 사람들에게는 계산대에서 가까운 쪽부터 대기열의 끝을 향해 번호가 매겨진다.

첫 번째 줄에 n명 모두를 처리하는 데 필요한 최소 시간을 나타내는 하나의 수를 출력한다. 이어지는 ⌈n / 2⌉개의 줄에 고객들이 응대받는 순서를 출력한다. 각 줄에는 아마 마지막 줄을 제외하고, 현재 처리 단계에서 응대받을 고객들의 번호인 두 수를 공백으로 구분하여 출력해야 한다. n이 홀수라면 마지막 줄에는 대기열에서 마지막으로 응대받는 고객의 번호인 하나의 수를 출력해야 한다. 고객 번호는 1부터 시작한다.