题目描述

有一序列 $x$ ，长度为 $q$ ，序列中的每个数只出现一次。

即：序列 $x$ 是 $1$ 到 $q$ 的一个排列。

对于序列 $x$ 的操作只有一种：对于一个数 $x_i$ ，你可以使其与 $x_{2i}$ 或 $x_{2i+1}$ 交换位置(如果它们存在的话)。

现在请你使序列 $x$ 变为一个升序序列，并按顺序输出你进行的操作。

输入格式

输入数据共 $2$ 行。

第 $1$ 行， $1$ 个正整数，$q$。

第 $2$ 行， $q$ 个正整数， $x_{1～q}$。

输出格式

输出数据共 $ans$ 行， $ans$ 表示你的操作次数。

第 $1$ ~ $ans$ 行，每行两个整数，$i$ ，$j$ ，表示交换 $x_i$ 和 $x_j$ 的位置 $(i < j)$。

3
3 1 2

1 3
1 2

7
1 3 2 7 6 4 5

2 4
1 2
1 3
3 7
2 5
1 2
1 3
3 6
1 2
2 5
1 3
1 2
2 4
1 2
1 3
1 2

提示

【样例说明】

样例#1说明：

交换 $2$ 和 $3$ ，序列变为：$2,1,3$。

再交换 $2$ 和 $1$ ，序列变为：$1,2,3$。

【数据范围】

对于 $40\%$ 的数据，$3 \le q \le 2^{10}$。

对于 $100\%$ 的数据，$3 \le q \le 2^{17}$，$1 \le x_i \le q$。

【提示】

• 使用 Special Judge。
• $q = 2 ^ p - 1(p \in \mathbb{N}^*)$
• 最多进行 $2q\times\lceil\log_2 q\rceil$ 次操作。
• 样例的输出数据只是众多方案中的一种。
• 因为是 special judge ，因此不提供附加样例。

【文件读入读出】（模拟，提交代码时不需使用）

• 文件名：sequence.cpp
• 读入文件名：sequence.in
• 读出文件名：sequence.out