Given a strip of checkered paper with a length of N cells and a width of 1 cell, in which some cells are painted black, and the rest — into white. Such a stripe is called a palindrome if the sequence of black and white cells when viewed from left to right is the same as when viewed from right to left.
You are given a strip of length N. You need to cut it into strips that are palindromes so that the number of resulting strips is strictly less than (2/5)N + 3.
Input
The first line of the input file contains the number N — the length of the original strip (N — a natural number not exceeding 100000). Next comes N numbers describing the coloring of the strip: 0 means a black cell, and 1 — white.
Imprint
In the output file print in ascending order the numbers of the cells of the original strip, after which you need to make cuts.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
6
0 1 0 1 1 0
| 3 5 |
From the original strip, we will get 3 palindrome strips by making cuts after the 3rd cell (that is, between the 3rd and 4th) and after the 5th (that is, between the 5th and 6th)< /td>
|
| 2 |
6
0 1 1 0 0 0
| 1 3 |
This strip can be cut into 2 palindrome strips, however, according to the condition, it is not required to look for a solution with a minimum number of resulting strips — it is enough that the number of strips satisfies the restriction specified in the condition. |
| 3 |
5
0 0 0 0 0
| |
The original string is already a palindrome, so nothing can be cut |