Minimizing Distinct Subset Sums

Given a positive integer (n), you are required to construct a set (S) of size (n) with the following properties:

1. Every element of (S) is an integer in the range ([-10^9, 10^9]).
2. Define [ \Omega(S)=\left{ x \mid x=\sum_{i\in T}i,; T\subseteq S,; T\neq \varnothing \right}. ] That is, (\Omega(S)) is the set of all non-empty subset sums of (S). Your task is to choose (S) so that (|\Omega(S)|) is minimized.

Note: You do not need to prove that your construction is optimal. Any set (S) satisfying the above conditions and believed to minimize (|\Omega(S)|) is accepted.

A simple construction that works is based on symmetry:

• If (n) is odd, let (S = {0, 1, -1, 2, -2, \dots, k, -k}) where (k = \frac{n-1}{2}).
• If (n) is even, let (S = {1, -1, 2, -2, \dots, k, -k}) where (k = \frac{n}{2}).

This construction ensures many cancellations among subset sums. For example, when (n=3), choose (S = {0, 1, -1}) so that (\Omega(S) = {-1, 0, 1}).

Your program only needs to output any valid set (S) (the order of printed elements does not matter).

inputFormat

The input consists of a single line containing a positive integer (n) ((1 \le n \le 10^5)).

outputFormat

Output a set (S) of (n) integers (each separated by a space) that satisfies the constraints and minimizes (|\Omega(S)|) under the construction described.

sample

3

-1 0 1