A Preponderant Reunion
Contest: Codeforces Round 462 (Div. 1)
Difficulty rating: 3200
Tags: constructive algorithms, dp

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 p1, p2, ..., pn 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, pi and pi + 1 (1 ≤ i < n), and then decrease them by their minimum (i. e. min(pi, pi + 1)), the cost of this operation is equal to min(pi, pi + 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 format:
The first line contains one integer n (1 ≤ n ≤ 3·105).

The second line contains n space-separated integers p1, p2, ..., pn (0 ≤ pi ≤ 109, i = 1, 2, ..., n).

Output format:
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 pi and pi + 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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, one possible best solution is $$\begin{bmatrix}
2 & 1 & 3 & 1
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 3 & 1
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 2 & 0
\end{bmatrix}$$, of which the cost is 1 + 1 = 2.

In the second sample, one possible best solution is $$\begin{bmatrix}
2 & 2 & 1 & 3 & 1
\end{bmatrix}
\rightarrow
\begin{bmatrix}
2 & 1 & 0 & 3 & 1
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 0 & 3 & 1
\end{bmatrix}
\rightarrow
\begin{bmatrix}
1 & 0 & 0 & 2 & 0
\end{bmatrix}$$, of which the cost is 1 + 1 + 1 = 3.

Example input:
4
2 1 3 1

Example output:
2
1
3

Example input:
5
2 2 1 3 1

Example output:
3
2
1
4

Editorial:
The author was inspired by 100705B1 - Rasta-making and then made this problem.
Noticing that there are no two consecutive positive integers after the game ends, the final sequence can be divided into some intervals which consist only zero elements such that the gap between every two adjacent intervals is at most one element (may positive).
Let's try to solve a general version of this problem first. In this version, we don't need to decrease two consecutive positive integers by their minimum. We can decrease any two consecutive integers by 1 many times (even if integers are negative) and our task is to eliminate all two consecutive positive integers such that the cost as small as possible.
We can prove by contradiction or adjustment that there are no negative elements in the best solution for the general version (because the original elements are non-negative). Furthermore, the cost of the best solution for the general version is less or equal to that of the best solution for the original version.
Let's consider the cost for the general version to make such an interval [l, r] (i. e. pl, pl + 1, ..., pr) become all non-positive (1 ≤ l ≤ r ≤ n). Before concluding the formula, you may assume p0 = pn + 1 = 0.
Let cl = pl,  ci = max(pi - ci - 1, 0) (i = l + 1, l + 2, ..., r). We can construct a series of operations to make them become non-positive such that the cost can be represented as $$\sum_{i=1}^{n} c_i$$. Let's call the cost of such an interval [l, r] as f(l, r). Similarly, we know the actual minimal cost is less or equal to f(l, r).
If the length of an interval [l, r] is greater than 2, there is an observation that
We can easily prove that f(l, r) is the actual minimal cost in the cases of length 1 and 2. In addition, if we get any of the best solutions for the general version, we can construct a series of operations which is valid both in the general version and the original version. So we can conclude that the cost of the best solution for the general version is greater or equal to that for the original version. With one conclusion we mentioned above, we know that the minimal costs for the original version and the general version are equivalent.
Denote dp(i) as the minimum cost the first i elements have used if the i-th element is going to be the right endpoint of such an interval. It's easy to compute dp(n) in $${\mathcal{O}}(n)$$.
After picking up all the intervals for the best solution, construction can be implemented by greedy. For example, utilize the descensions at the inner of intervals first, and then make use of the descensions at the edge of intervals.
Please note that there may be at most one element that belongs to no interval at the head or the tail of the final sequence. Also, the descensions should operate on positive integers.