D. Два из трех
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Недавно Вася разрабатывал новый алгоритм по оптимизации приема клиентского потока и рассматривал следующую задачу.

Пусть в очереди к кассе стоят n человек, причем, каждый характеризуется положительным целым числом ai — временем обработки этого клиента. Особенность же данной конкретной кассы в том, что она способна принять двух клиентов одновременно, причем время обработки двух клиентов со временами ai и aj равно max(ai, aj). Обратите внимание, что обработка — это непрерываемый процесс, и поэтому, если два человека одновременно обслуживаются в кассе, то это значит, что они одновременно начали обрабатываться, и одновременно закончат (возможно, что одному из них придется подождать).

Вася в своем алгоритме использовал гениальную эвристику — пока в очереди больше одного человека на обработку посылаются одновременно какие-то два человека из первых трех, стоящих в начале очереди. В случае, если в очереди остается единственный клиент номер i, то он проходит в кассу, и его обслуживание занимает ai времени. Заметим, что общее количество фаз обработки будет всегда равно n / 2⌉ (операция x означает округление вверх до ближайшего целого числа).

Вася считает, что этот метод поможет справиться со столь ненавистными всем очередями, и поэтому попросил Вас разработать программу, которая определит минимальное время, за которое обработается вся очередь с помощью этого алгоритма.

Входные данные

В первой строке входного файла содержится единственное число n (1 ≤ n ≤ 1000) — количество людей в последовательности. Во второй строке через пробел записаны целые числа a1, a2, ..., an (1 ≤ ai ≤ 106). Люди занумерованы начиная от кассы к концу очереди.

Выходные данные

В первую строку выведите единственное число — минимальное время, за которое будут обработаны все n человек. Далее в n / 2⌉ строках выведите порядок, в котором будут обрабатываться клиенты. Каждая строка (кроме, возможно, последней) должна содержать два числа через пробел — номера клиентов, которые на текущем шаге пройдут на обработку. Если n — нечетно, то последняя строка должна содержать единственное число — номер последнего обработанного человека в очереди. Клиенты нумеруются начиная с 1, числа в строках разрешается выводить в любом порядке.

Примеры
Входные данные
4
1 2 3 4
Выходные данные
6
1 2
3 4
Входные данные
5
2 4 3 1 4
Выходные данные
8
1 3
2 5
4