English · Original
Chinese · Translation
Formal · Original
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.
## Input
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.
## Output
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.
[samples]
Vasya 最近开发了一种优化顾客流接收的新算法，他考虑了以下问题。
假设收银台前的队列中有 #cf_span[n] 个人，每个人用一个正整数 #cf_span[ai] 表示服务该顾客所需的时间。这个收银台的特殊之处在于它可以同时服务两位顾客。然而，如果两位顾客分别需要 #cf_span[ai] 和 #cf_span[aj] 的时间，那么服务这两位顾客所需的总时间为 #cf_span[max(ai, aj)]。请注意，服务顾客是一个不可中断的过程，因此，如果两位顾客同时到达收银台，他们将同时开始被服务，并同时结束（其中一人可能需要等待）。
Vasya 在他的算法中使用了一种巧妙的启发式方法：只要队列中仍有超过一人等待，就从队列最前面的三人中选出两人同时服务。如果队列中只剩一位顾客 #cf_span[i]，则他单独前往收银台，耗时 #cf_span[ai] 被服务。注意，服务所有顾客的总阶段数始终等于 #cf_span[⌈n / 2⌉]。
Vasya 认为这种方法将有助于解决我们所有人讨厌的排队问题。因此，他请你编写一个程序，确定使用该算法服务整个队列所需的最短时间。
输入文件的第一行包含一个单独的数字 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000])，表示队列中的人数。第二行包含用空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 106])。人们从收银台开始向队列末尾编号。
请在第一行输出一个单独的数字——服务所有 #cf_span[n] 个人所需的最短时间。然后在 #cf_span[⌈n / 2⌉] 行中输出顾客被服务的顺序。每行（可能除了最后一行）必须包含两个用空格分隔的数字——当前处理阶段中将被服务的顾客编号。如果 #cf_span[n] 为奇数，则最后一行必须包含一个数字——队列中最后一位被服务的顾客编号。顾客编号从 #cf_span[1] 开始。
## Input
输入文件的第一行包含一个单独的数字 #cf_span[n] (#cf_span[1 ≤ n ≤ 1000])，表示队列中的人数。第二行包含用空格分隔的整数 #cf_span[a1, a2, ..., an] (#cf_span[1 ≤ ai ≤ 106])。人们从收银台开始向队列末尾编号。
## Output
请在第一行输出一个单独的数字——服务所有 #cf_span[n] 个人所需的最短时间。然后在 #cf_span[⌈n / 2⌉] 行中输出顾客被服务的顺序。每行（可能除了最后一行）必须包含两个用空格分隔的数字——当前处理阶段中将被服务的顾客编号。如果 #cf_span[n] 为奇数，则最后一行必须包含一个数字——队列中最后一位被服务的顾客编号。顾客编号从 #cf_span[1] 开始。
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of customers.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the service time of customer $ i $.
Let $ k = \left\lceil \frac{n}{2} \right\rceil $ be the number of service phases.
**Constraints**
1. $ 1 \leq n \leq 1000 $
2. $ 1 \leq a_i \leq 10^6 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Minimize the total service time $ T $, defined as the sum of the maximum service time in each phase:
$$
T = \sum_{j=1}^{k} \max\{a_{i}, a_{j}\} \quad \text{(for the pair served in phase } j\text{)}
$$
where each customer is served in exactly one phase, and in each phase, either one or two customers are served:
- If two customers $ i $ and $ j $ are served together in a phase, their combined service time is $ \max(a_i, a_j) $.
- If one customer $ i $ is served alone, their service time is $ a_i $.
Additionally, in each phase (except possibly the last), the two customers served must be chosen from the first three customers remaining in the queue (i.e., the earliest remaining customers).
**Output Requirement**
Find a sequence of $ k $ phases (each containing one or two customer indices) such that:
- The total time $ T $ is minimized.
- At each phase, the selected customer(s) are among the first three in the current queue.
- Output the sequence of phases: each line contains the indices (1-based) of the customers served in that phase (two numbers if paired, one if alone).
API Response (JSON)
{
"problem": {
"name": "D. Two out of Three",
"description": {
"content": "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 ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF82D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "Vasya has recently developed a new algorithm to optimize the reception of customer flow and he considered the following problem.\n\nLet the queue to the cashier contain _n_ people, at that each of them ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "Vasya 最近开发了一种优化顾客流接收的新算法，他考虑了以下问题。\n\n假设收银台前的队列中有 #cf_span[n] 个人，每个人用一个正整数 #cf_span[ai] 表示服务该顾客所需的时间。这个收银台的特殊之处在于它可以同时服务两位顾客。然而，如果两位顾客分别需要 #cf_span[ai] 和 #cf_span[aj] 的时间，那么服务这两位顾客所需的总时间为 #cf_span[max(a...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the number of customers. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers, where $ a_i $ is the service time of customer $ i $. ...",
"is_translate": false,
"language": "Formal"
}
]
}