[FJOI2015]金币换位问题

时间限制:10s      空间限制:128MB

题目描述

给定一个n,最开始序列长这样:
1111...10000...0__
n个1,n个0,两个空格
现在要求用最少的交换步数,使得最终的序列为
1010...1010__
就是前2n个都是10交替
所谓交换是指将相邻两个非空格的数一起挪到两个空格上。例如,下面是n=4时的一组合法解
11110000__
__11000011
101__00011
1010100__1
10101__001
10101010__


输入格式

输入一个n


输出格式

第一行输出最少移动步数
接下来一行为移动方案,只要输出被移动的两个非空格格子左边那个的编号。换不换行无所谓。详见样例。


样例输入

4

样例输出

5
1 4 8 6 9

提示

对于100%的数据,2<n<=200000


题目来源

没有写明来源

Menuappsclose