← 返回题目列表

Codeforces · 82/D

D. 三分之二

中文机器翻译题面 查看原题

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 开始。

示例

输入 #1

4
1 2 3 4

输出 #1

6
1 2
3 4

输入 #2

5
2 4 3 1 4

输出 #2

8
1 3
2 5
4