解题思路

1. 目标函数按位拆分

设需要构造两两不同的正整数序列 $b_1,\dots,b_n$。 目标为最小化

题目内容

给定一个正整数 $n$ 。请你构造一个长度为 $n$ 的数组 {$b_1,b_2,...,b_n$} 满足：

• 所有元素两两不同；

• 令目标函数为 $\sum _{1≤i≤j≤n}(b_i$ $xor$ $b_j)$ ，需要使该值尽可能小。

$xor$ 表示按位异或运算。上式的含义是把所有不同下标对的异或值相加。

输入描述

一行输入一个整数 $n (2 ≦n≦2× 10^5)$ 。

输出描述

输出 $n$ 个正整数，表示你构造出的数组元素。若有多种最优解，输出任意一种即可。要求每个 $b_i$ 满足 $1 ≦ b_i≦ 2^{31} - 1$ 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确，注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

3

输出

4 5 6

说明

对于 $b=${$4,5,6$}，三对异或分别为:$4$ $xor$ $5=1,4$ $xor$ $6=2,5$ $xor$ $6=3$ ,总和为 $1+2+3=6$ 。

样例2

输入

2

输出

6 7