English · Original
Chinese · Translation
Formal · Original
_East or west, home is best. That's why family reunion, the indispensable necessity of Lunar New Year celebration, is put in such a position._
After the reunion dinner, Little Tommy plays a game with the family. Here is a concise introduction to this game:
1. There is a sequence of _n_ non-negative integers _p_1, _p_2, ..., _p__n_ in the beginning. It is ruled that each integer in this sequence should be non-negative **at any time**.
2. You can select two **consecutive positive** integers in this sequence, _p__i_ and _p__i_ + 1 (1 ≤ _i_ < _n_), and then decrease them by their minimum (i. e. _min_(_p__i_, _p__i_ + 1)), the cost of this operation is equal to _min_(_p__i_, _p__i_ + 1). We call such operation as a _descension_.
3. The game immediately ends when there are no two consecutive positive integers. Your task is to end the game so that the total cost of your operations is as small as possible.
Obviously, every game ends after at most _n_ - 1 descensions. Please share your solution of this game with the lowest cost.
## Input
The first line contains one integer _n_ (1 ≤ _n_ ≤ 3·105).
The second line contains _n_ space-separated integers _p_1, _p_2, ..., _p__n_ (0 ≤ _p__i_ ≤ 109, _i_ = 1, 2, ..., _n_).
## Output
In the first line print one integer as the number of descensions _m_ (0 ≤ _m_ ≤ _n_ - 1).
In the next _m_ lines print the descensions chronologically. More precisely, in each line of the next _m_ lines print one integer _i_ (1 ≤ _i_ < _n_) representing a descension would operate on _p__i_ and _p__i_ + 1 such that all the descensions could be utilized from top to bottom.
If there are many possible solutions to reach the minimal cost, print any of them.
[samples]
## Note
In the first sample, one possible best solution is , of which the cost is 1 + 1 = 2.
In the second sample, one possible best solution is , of which the cost is 1 + 1 + 1 = 3.
_东或西，家最宜。因此，团圆——春节不可或缺的必要环节——被置于如此重要的位置。_
团圆饭后，小汤米与家人玩了一个游戏。以下是该游戏的简要介绍：
显然，每场游戏最多经过 #cf_span[n - 1] 次降阶后结束。请分享你以最低代价完成该游戏的解法。
第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 3·105)]。
第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[p1, p2, ..., pn] #cf_span[(0 ≤ pi ≤ 109, i = 1, 2, ..., n)]。
第一行输出一个整数，表示降阶次数 #cf_span[m] #cf_span[(0 ≤ m ≤ n - 1)]。
接下来的 #cf_span[m] 行按时间顺序输出每次降阶操作。更准确地说，在接下来的 #cf_span[m] 行中，每行输出一个整数 #cf_span[i] #cf_span[(1 ≤ i < n)]，表示一次作用于 #cf_span[pi] 和 #cf_span[pi + 1] 的降阶操作，且所有降阶操作需按从上到下的顺序依次执行。
若存在多个能达到最小代价的解，请输出其中任意一个。
在第一个样例中，一种可能的最优解是 ，其代价为 #cf_span[1 + 1 = 2]。
在第二个样例中，一种可能的最优解是 ，其代价为 #cf_span[1 + 1 + 1 = 3]。
## Input
第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 3·105)]。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[p1, p2, ..., pn] #cf_span[(0 ≤ pi ≤ 109, i = 1, 2, ..., n)]。
## Output
第一行输出一个整数，表示降阶次数 #cf_span[m] #cf_span[(0 ≤ m ≤ n - 1)]。接下来的 #cf_span[m] 行按时间顺序输出每次降阶操作。更准确地说，在接下来的 #cf_span[m] 行中，每行输出一个整数 #cf_span[i] #cf_span[(1 ≤ i < n)]，表示一次作用于 #cf_span[pi] 和 #cf_span[pi + 1] 的降阶操作，且所有降阶操作需按从上到下的顺序依次执行。若存在多个能达到最小代价的解，请输出其中任意一个。
[samples]
## Note
在第一个样例中，一种可能的最优解是 ，其代价为 #cf_span[1 + 1 = 2]。在第二个样例中，一种可能的最优解是 ，其代价为 #cf_span[1 + 1 + 1 = 3]。
**Definitions**
Let $ n \in \mathbb{Z} $ be the number of elements.
Let $ P = (p_1, p_2, \dots, p_n) $ be a sequence of non-negative integers, where $ p_i \in \mathbb{Z}_{\geq 0} $ for all $ i \in \{1, \dots, n\} $.
A *descension* on index $ i $ (where $ 1 \leq i < n $) is an operation that reduces both $ p_i $ and $ p_{i+1} $ by 1, at a cost of 1.
**Constraints**
1. $ 1 \leq n \leq 3 \cdot 10^5 $
2. $ 0 \leq p_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
3. At most $ n - 1 $ descensions may be performed.
**Objective**
Find a sequence of descensions (each specified by an index $ i \in \{1, \dots, n-1\} $) such that:
- The final values $ p_1', p_2', \dots, p_n' $ satisfy $ p_1' = p_2' = \dots = p_n' $,
- The total cost (number of descensions) is minimized.
Output:
- The number of descensions $ m $,
- The sequence of $ m $ indices (in chronological order) describing the descensions performed.
API Response (JSON)
{
"problem": {
"name": "E. A Preponderant Reunion",
"description": {
"content": "_East or west, home is best. That's why family reunion, the indispensable necessity of Lunar New Year celebration, is put in such a position._ After the reunion dinner, Little Tommy plays a game with",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF933E"
},
"statements": [
{
"statement_type": "Markdown",
"content": "_East or west, home is best. That's why family reunion, the indispensable necessity of Lunar New Year celebration, is put in such a position._\n\nAfter the reunion dinner, Little Tommy plays a game with...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "_东或西，家最宜。因此，团圆——春节不可或缺的必要环节——被置于如此重要的位置。_\n\n团圆饭后，小汤米与家人玩了一个游戏。以下是该游戏的简要介绍：\n\n显然，每场游戏最多经过 #cf_span[n - 1] 次降阶后结束。请分享你以最低代价完成该游戏的解法。\n\n第一行包含一个整数 #cf_span[n] #cf_span[(1 ≤ n ≤ 3·105)]。\n\n第二行包含 #cf_span[n] 个用...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z} $ be the number of elements. \nLet $ P = (p_1, p_2, \\dots, p_n) $ be a sequence of non-negative integers, where $ p_i \\in \\mathbb{Z}_{\\geq 0} $ for all $ i \\in...",
"is_translate": false,
"language": "Formal"
}
]
}