Optimal District Heights

In this problem, you are given a sequence of n districts. For each district i (1 ≤ i ≤ n), you are also given a maximum allowable height ( b_i ). Your task is to assign each district a height ( h_i ) such that the following conditions are satisfied:

1. ( 1 \leq h_i \leq b_i ) for all ( i ).
2. No two consecutive districts have the same height, i.e., ( h_i \neq h_{i+1} ) for all ( 1 \leq i < n ).
3. The total height difference between consecutive districts, given by ( \sum_{i=1}^{n-1} |h_i-h_{i+1}| ), is minimized.

A simple alternating assignment between 1 and 2 (starting with 1) yields an optimal solution for the provided constraints. For example, if ( n=4 ) and ( b = [4, 3, 5, 2] ), one valid optimal assignment is ( [1,2,1,2] ).

inputFormat

The input is given via standard input (stdin). The first line contains a single integer ( n ) representing the number of districts. The second line contains ( n ) space-separated integers ( b_1, b_2, \dots, b_n ) where each ( b_i ) is the maximum allowable height for district ( i ).

outputFormat

Output a single line on standard output (stdout) containing ( n ) space-separated integers representing the optimal height assignment for the districts.## sample

4
4 3 5 2

1 2 1 2