题目描述

给定一个 $n$，最开始序列长这样：

现在要求用最少的交换步数，使得最终的序列为

所谓交换是指将相邻两个非空格的数一起挪到两个空格上。

例如，下面是 $n=4$ 时的一组合法解：

• 初始状态：$\verb!11110000__!$。
• 第 $1$ 步：$\verb!__11000011!$。
• 第 $2$ 步：$\verb!101__00011!$。
• 第 $3$ 步：$\verb!1010100__1!$。
• 第 $4$ 步：$\verb!10101__001!$。
• 第 $5$ 步：$\verb!10101010__!$。

可以证明，最少的操作次数就是 $5$ 步。

输入格式

输入共一行一个整数 $n$。

输出格式

第一行输出最少移动步数。

接下来一行为移动方案，只要输出被移动的两个非空格格子左边那个的编号。详见样例。

4

5
1 4 8 6 9

提示

对于 $100\%$ 的数据，$2<n\le 2\times 10^5$。