题目内容

一个长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 被称为“钝化”序列，如果对于任意三个不同的下标 $i, j, k$，将对应的元素按非降序排列为 $x \le y \le z$ 后，都满足 $x + y \le z$。

请构造一个长度为 $n$ 的钝化序列，要求序列中每个元素均为正整数且不超过 $10^9$。如果无法构造，则报告无解。

约束：数组长度 $n$ 满足 $3 \le n \le 2 \times 10^5$，每个元素满足 $1 \le a_i \le 10^9$。

输入描述

输入仅一行，包含一个整数 $n$，表示需要构造的序列长度。

输出描述

如果存在满足条件的钝化序列，则输出一行，包含 $n$ 个用空格分隔的整数；否则输出 $-1$。若方案不唯一，输出任意一个均可。

样例1

输入

3

输出

1 1 2

说明

当序列长度为 3 时，取斐波那契式数列的前 3 项 1, 1, 2。排序后满足 $1+1 \le 2$，因此是一个合法的钝化序列。

样例2

输入

6

输出

1 1 2 3 5 8

说明

构造一个类斐波那契数列，前 6 项为 1, 1, 2, 3, 5, 8。任意挑选三个数排序为 $x \le y \le z$，均有 $x+y \le z$，例如 $2+3 \le 5$。满足条件。

样例3

输入

44

输出

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155 165580141 267914296 433494437 701408733

说明

44 是满足元素不超过 $10^9$ 时能构造的最大长度。完整的斐波那契数列为 1, 1, 2, ... , 701408733。任意三个元素满足 $x+y \le z$，故该序列合法。

样例4

输入

45

输出

-1

说明

在元素上限 $10^9$ 下，钝化序列的最长可构造长度为 44。当需要长度 45 时，无法找到符合条件的序列，因此输出 -1。