Minimize Prefix Sum Sequence

Given a positive integer N, construct an array A of length N such that for every index \(i\) (with \(1 \leq i \leq N\)), the element A[i] is either \(1\) or \(-1\) (i.e. \(A_i \in \{1, -1\}\)).

For this array, define the prefix sum \(P_i\) as:

[ P_i = \sum_{j=1}^{i} A_j ]

Your task is to construct the array so that the sum of all prefix sums, i.e.,

[ S = \sum_{i=1}^{N} P_i ]

is minimized. If multiple solutions exist, output the one that starts with \(1\) and follows an alternating pattern.

For example:

• When \(N = 3\), one valid output is: 1 -1 1.
• When \(N = 4\), one valid output is: 1 -1 1 -1.

inputFormat

The input consists of a single integer N (N > 0), read from standard input.

outputFormat

Output the constructed array \(A\) as a sequence of N numbers separated by a single space to standard output.

## sample

3

1 -1 1