Under construction

Still being built. Things may change

Beautiful Sequence

Interview

Time limit1sMemory limit256 MB

Summary
Given N, print a sequence of N ones and N minus ones that maximizes the final value B_N of the recurrence B_i = B_(i-1) * A_(2i-1) + A_(2i).
Level

Medium5 of 10

Topics
Greedy, Math, Implementation
Solved
No attempts yet

Problem

For a sequence AA of length 2N2N, its beauty b(A)b(A) is defined as follows.

Bi={0,i=0Bi−1×A2i−1+A2i1≤i≤NB_i = \begin{cases} 0, & i=0 \\ B_{i-1} \times A_{2i-1} + A_{2i} & 1 \le i \le N \end{cases}

b(A)=BNb(A) = B_N

Print the sequence with the maximum beauty among the sequences that satisfy the conditions below.

  • The length of the sequence is 2N2N.
  • Exactly NN of its elements are 1, and the other NN elements are -1.

Input

The first line contains NN.

Output

Print the sequence with the maximum beauty, with each term separated by a space.

Constraints

  • 1≤N≤1051 \le N \le 10^5

Examples1

  1. Example 1

    Input
    1
    Expected output
    -1 1