On a test, N students sit in a row. For each student, it is known what grade he would have received if he had written this control independently (the grade — is a number from 2 to 5). However, students can write the control not only on their own, but also copy from their neighbor, but only if the neighbor writes the control on their own. In this case, the cheater will receive the same grade as the one from whom he cheated.
Namely (rules are applied strictly in the specified order):
- Students who know the material at 5 will write the test on their own.
- A student who knows the material at 4, if he sits next to someone who knows at 5, will copy from him, otherwise he will write on his own.
- A student who knows 3, if he sits next to someone who knows 5, will cheat from him. If among his neighbors there is no one who knows for 5, but there is one who knows for 4, and at the same time writes on his own, then the C student will write off from him. Otherwise it will write itself.
- Similarly, a schoolboy who knows 2 — from the neighbors who write on their own, he will choose the one who knows best, and write off from him. And if there are none (or both of his neighbors also know 2), then he will write on his own.
Decide who gets what grade.
Input
The number N (1<=N<=10) is entered - the number of students, and then a sequence of N numbers describing who can write a test for what grade if they write on their own.
Imprint
Output N numbers - grades that students will get for the test.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
5
5
2
3
4
5 |
5
5
3
5
5 |
The first and fifth students will write on their own. The second will write off the first, and the fourth — at the fifth (as a result, they will also receive fives). The third person has no one to write off from, since his neighbors will not write the work on their own. |
| 2 |
6
2
2
3
2
2
4 |
2
3
3
3
4
4 |
The second and fourth will be written off from the third, the fifth — at the sixth. |