CF82D.Two out of Three

Vasya has recently developed a new algorithm to optimize the reception of customer flow and he considered the following problem.

Let the queue to the cashier contain n people, at that each of them is characterized by a positive integer a__i — that is the time needed to work with this customer. What is special about this very cashier is that it can serve two customers simultaneously. However, if two customers need a__i and a__j of time to be served, the time needed to work with both of them customers is equal to max(a__i, a__j). Please note that working with customers is an uninterruptable process, and therefore, if two people simultaneously come to the cashier, it means that they begin to be served simultaneously, and will both finish simultaneously (it is possible that one of them will have to wait).

Vasya used in his algorithm an ingenious heuristic — as long as the queue has more than one person waiting, then some two people of the first three standing in front of the queue are sent simultaneously. If the queue has only one customer number i, then he goes to the cashier, and is served within a__i of time. Note that the total number of phases of serving a customer will always be equal to ⌈n / 2⌉.

Vasya thinks that this method will help to cope with the queues we all hate. That's why he asked you to work out a program that will determine the minimum time during which the whole queue will be served using this algorithm.

瓦西娅最近开发了一种新算法，用于优化客户流的接待，并考虑了如下问题：

设收银台前的队列中有 $n$ 位顾客，每位顾客 $i$ 由一个正整数 $a_i$ 表征——即服务该顾客所需的时间。该收银台的特殊之处在于：它可同时服务两位顾客。然而，若两位顾客分别需要 $a_i$ 和 $a_j$ 的时间完成服务，则同时服务这两位顾客所需的时间为 $\max(a_i,\,a_j)$。请注意，服务过程是不可中断的；因此，若两位顾客同时到达收银台，则他们将同时开始被服务，并同时结束服务（其中一人可能需等待）。

瓦西娅在其算法中采用了一种巧妙的启发式策略：只要队列中尚有超过一位顾客在等待，就从当前排在队列最前面的三人中选出两人，让他们同时前往收银台接受服务。若队列中仅剩一位顾客（编号为 $i$），则他单独前往收银台，耗时 $a_i$ 完成服务。注意，整个服务过程的阶段总数恒为 $\lceil n\,/\,2 \rceil$。

瓦西娅认为，这种方法有助于缓解我们所有人都深恶痛绝的排队问题。因此，他请你编写一个程序，计算出：使用该算法服务完整个队列所需的最短总时间。

The first line of the input file contains a single number n (1 ≤ n ≤ 1000), which is the number of people in the sequence. The second line contains space-separated integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 106). The people are numbered starting from the cashier to the end of the queue.

输入文件的第一行包含一个整数 $n$（$1 \leq n \leq 1000$），表示队列中的人数。第二行包含 $n$ 个用空格分隔的整数 $a_1,\,a_2,\,\dots,\,a_n$（$1 \leq a_i \leq 10^6$）。队列中的人从收银员开始编号，依次向队尾编号。

Print on the first line a single number — the minimum time needed to process all n people. Then on ⌈n / 2⌉ lines print the order in which customers will be served. Each line (probably, except for the last one) must contain two numbers separated by a space — the numbers of customers who will be served at the current stage of processing. If n is odd, then the last line must contain a single number — the number of the last served customer in the queue. The customers are numbered starting from 1.

第一行输出一个整数——处理全部 $n$ 位顾客所需的最短时间。随后在 $\lceil n\,/\,2 \rceil$ 行中输出顾客被服务的顺序。每行（最后一行除外）必须包含两个用空格分隔的数字——表示当前处理阶段将被服务的两位顾客的编号。若 $n$ 为奇数，则最后一行仅包含一个数字——队列中最后一位被服务的顾客的编号。顾客编号从 $1$ 开始。