The city of Hanoi has towers, arranged in a line, numbered from
to
. Each one of the towers can be in one of two states: occupied or empty.
You have the ability to toggle the state of a tower of your choice (i.e. empty an occupied tower or occupy an empty tower). But when you do so, towers that are directly adjacent also toggle their state indirectly. Note that if you toggle tower , only towers
and
are toggled. The situation is similar for tower
: if you toggle tower
, only towers
and
are toggled.
You are given the task of emptying all towers. Can you accomplish this task in at most
steps?
It is guaranteed that this task is possible for the test cases given.
If there are multiple ways to do so, output any one of them.
Constraints
Subtask 1 [20%]
Subtask 2 [30%]
Subtask 3 [50%]
Input Specification
The first line of input will contain an integer .
The second line of input will contain space-separated integers. The
integer will contain the state of tower numbered
. A
1
indicates the tower is occupied and a 0
indicates the tower is empty.
Output Specification
On the first line, print the total number of steps that you will take. If this number is larger than , the judge will not accept your output.
On the following lines, print the steps that you will take in order, one on each line. For each step, output the number of the tower that should be directly toggled on that step.
Sample Input 1
6
0 1 1 1 0 0
Sample Output 1
1
3
Sample Input 2
7
1 0 1 1 1 1 1
Sample Output 2
3
1
3
6
Comments
In the problem set you said if you toggle
you toggle
&
that means you toggle
and
not
and
? or am i wrong ?
The problem statement refers to the fact that toggling a tower also toggles those adjacent. Tower
is only adjacent to tower
, since there is no tower
, and tower
is only adjacent to tower
. This exception exists only for towers
and
, since all other towers have two others adjacent, one in front and one behind.