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? |
source: http://pixabay.com/en/saw-chainring-chainsaw-chain-wood-5901/ |

Constraints of the domino effect:

- The height of the ith tree is H[i], 1 <= i <= N
- If tree i falls left then all standing trees j fall left as well for i-H[i] < j < i
- If tree i falls right then all standing trees j fall right as well for i < j < i+H[i]
- A tree can only fall once

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

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.

Input | Output |
---|---|

5 1 2 3 1 1 |
Two of the possible outputs are 2 3 -2or 2 1 2 |