首先分析答案下界，明显对于每一位独立考虑，那么肯定是前面全部放 \(0\)，后面全部放 \(1\)，这样这一位的贡献是 \(1\) 的个数除以 \(2\) 级别的，答案不可能比这个更优了。
那么此时只需要构造方案尝试达到这个下界即可。
一个小技巧是，注意到为了让高位满足条件，我们的相对顺序不会改变太多，按照每四个数分组考虑，发现此时对于第 \(k(k \ge 2)\) 位来说都是不变的，那么细心构造一下，发现交换第二个数和第三个数即可达到下界。
但是 \(n \bmod 4 = 2\) 的情况下这样构造只能达到下界 + 1，打表发现确实达不到下界，那么直接这样构造即可。
我记得新有对一个异或题也是按照四个数分类，这警示我们考察按位是否相同的题目按照某一固定块长，特别是 \(4\) 和 \(2\) 的正整数次幂分块，有奇效。
当时写了个每四个分块的做法发现 6 爆掉了于是就白兰了qwq