C. Lumberjack

A lumberjack has to cut down N trees which were planted along a straight line with fixed distance between them.

If the lumberjack cuts down a tree he can make it fall either left or right along the line. A tree can topple another tree if it falls on it and may cause the fall of many other trees (by the domino effect).

Which trees should the lumberjack cut down so that all trees fall with the minimum number of cuts?

   chainsaw
source:
http://pixabay.com/en/saw-chainring-chainsaw-chain-wood-5901/

Constraints of the domino effect:

Input

N
H[1] H[2] ... H[N]

Output

K
T[1] T[2] ... T[K]
K is the optimal number of tree cuts. The absolute value of T[i] is the index of the ith tree that is cut down. (Note that the order in which trees are cut down may matter.) T[i] is negative if tree T[i] falls left.

Example

Input Output
5
1 2 3 1 1

Two of the possible outputs are

2
3 -2
or
2
1 2