有 $$$n$$$ 硬币,标记为从 $$$1$$$ 到 $$$n$$$。最初,硬币 $$$c_i$$$ 位于位置 $$$i$$$ 并且面朝上(($$$c_1, c_2, \dots, c_n)$$$ 是从 $$$1$$$ 到 $$$n$$$ 的数字排列)。您可以对这些硬币进行一些操作。
在一次操作中,您可以执行以下操作:
- 选择 $$$2$$$ 不同的索引 $$$i$$$ 和 $$$j$$$。
- 然后,在 $$$i$$$ 和 $$$j$$$ 位置上交换硬币。
- 然后,将两个硬币翻转到 $$$i$$$ 和 $$$j$$$ 位置。 (如果它们最初是朝上的,则操作后它们将朝下,反之亦然)
构造一个最多 $$$n+1$$$ 操作的序列,以便在执行所有这些操作后,硬币 $$$i$$$ 将位于最后的位置 $$$i$$$ 上,面朝上。
请注意,您不需要最小化操作次数。
输入
第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — 硬币数量。
第二行包含 $$$n$$$ 整数 $$$c_1,c_2,\dots,c_n$$$ ($$$1 \le c_i \le n$$$, $$$c_i \neq c_j$$$ for $$$i\neq j$$$)。
输出
在第一行中,输出一个整数 $$$q$$$ $$$(0 \leq q \leq n+1)$$$ — 您使用的操作数。
在下面的 $$$q$$$ 行中,输出两个整数 $$$i$$$ 和 $$$j$$$ $$$(1 \leq i, j \leq n, i \ne j)$$$ — 您为当前操作选择的位置。
示例
输入 #1
3 2 1 3
输出 #1
3 1 3 3 2 3 1
输入 #2
5 1 2 3 4 5
输出 #2
0
注意
令面朝上的硬币 $$$i$$$ 表示为 $$$i$$$,面朝下的硬币 $$$i$$$ 表示为 $$$-i$$$。
第一个样本中执行的一系列动作改变了硬币,如下所示:
- $$$[~~~2,~~~1,~~~3]$$$
- $$$[-3,~~~1,-2]$$$
- $$$[-3,~~~2,-1]$$$
- $$$[~~~1,~~~2,~~~3]$$$
在第二个示例中,硬币已经处于正确的位置,因此无需交换。