← 返回题目列表

Codeforces · 933/E

E. 占优势的团聚

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

东方还是西方,家最好。所以,合家团圆这一过年必不可少的必需品,才被放在这样的位置。

吃完团圆饭,小汤米和家人一起玩游戏。下面简单介绍一下这款游戏:

1. 开头有一个 n 个非负整数 p1, p2, ..., pn 的序列。规定该序列中的每个整数在任何时候都应该是非负的。
2. 您可以在此序列中选择两个连续的正整数 pi 和 pi + 1 (1 ≤ i < n),然后将它们减去最小值(即 min(pi, pi + 1)),此操作的成本等于 min(pi, pi + 1)。我们将这种操作称为下降。
3. 当没有两个连续的正整数时,游戏立即结束。你的任务是结束游戏,使你的总运营成本尽可能小。

显然,每场比赛最多在 n - 1 次下降后结束。请分享您以最低成本解决此游戏的方案。

输入

第一行包含一个整数n (1 ≤ n ≤ 3·105)。

第二行包含 n 个空格分隔的整数 p1, p2, ..., pn (0 ≤ pi ≤ 109, i = 1, 2, ..., n)。

输出

在第一行中打印一个整数作为降序数 m (0 ≤ m ≤ n - 1)。

在接下来的 m 行中按时间顺序打印降级。更准确地说,在接下来的 m 行中的每一行中,打印一个整数 i (1 ≤ i < n) ,表示对 pi 和 pi + 1 进行下降操作,以便可以从上到下利用所有下降。

如果有多种可能的解决方案可以达到最低成本,请打印其中任何一个。

示例

输入 #1

4
2 1 3 1

输出 #1

2
1
3

输入 #2

5
2 2 1 3 1

输出 #2

3
2
1
4

注意

在第一个示例中,一个可能的最佳解决方案是 $$\begin{bmatrix}
2 & 1 & 3 & 1
\end{bmatrix}
\右箭头
\begin{bmatrix}
1 & 0 & 3 & 1
\end{bmatrix}
\右箭头
\begin{bmatrix}
1 & 0 & 2 & 0
\end{bmatrix}$$,其中成本为 1 + 1 = 2。

在第二个示例中,一个可能的最佳解决方案是 $$\begin{bmatrix}
2 & 2 & 1 & 3 & 1
\end{bmatrix}
\右箭头
\begin{bmatrix}
2 & 1 & 0 & 3 & 1
\end{bmatrix}
\右箭头
\begin{bmatrix}
1 & 0 & 0 & 3 & 1
\end{bmatrix}
\右箭头
\begin{bmatrix}
1 & 0 & 0 & 2 & 0
\end{bmatrix}$$,其中成本为 1 + 1 + 1 = 3。