AT_wtf22_day1_b.Non-Overlapping Swaps

给定一个 $ (1,2,\cdots,N) $ 的排列 $ P=(P_1,P_2,\cdots,P_N) $。

请你求出一组整数对序列 $ ((l_1,r_1),(l_2,r_2),\cdots,(l_k,r_k)) $，使其满足以下所有条件：

• 序列长度 $ k $ 满足 $ 0\leq k\leq N-1 $。
• $ 1\leq l_i\leq r_i\leq N $（$ 1\leq i\leq k $）。
• 对于每个 $ 1\leq i\leq k-1 $，有 $ r_{i+1}\leq l_i $ 或 $ r_i\leq l_{i+1} $。
• 经过以下操作 $ k $ 次后，$ P $ 能变为升序排列：
  • 第 $ i $ 次操作：交换 $ P_{l_i} $ 和 $ P_{r_i} $ 的值。如果 $ l_i=r_i $，则什么也不做。

在本题的约束下，必然存在满足条件的序列。

对于每个输入文件中的 $ T $ 个测试用例，请输出答案。

输入以如下格式从标准输入读入：

$ T $ $ case_1 $ $ case_2 $ $ \vdots $ $ case_T $

每个测试用例 $ case_i $ 的格式如下：

$ N $ $ P_1 $ $ P_2 $ $ \cdots $ $ P_N $

对于每个测试用例，输出如下格式的答案：

$ k $ $ l_1 $ $ r_1 $ $ l_2 $ $ r_2 $ $ \vdots $ $ l_k $ $ r_k $

如果有多组解，输出任意一组都视为正确。

约束

• $ 1\leq T\leq 250000 $
• $ 1\leq N\leq 250000 $
• $ P=(P_1,P_2,\cdots,P_N) $ 是 $ (1,2,\cdots,N) $ 的一个排列
• 每个输入文件中所有 $ N $ 的总和不超过 $ 250000 $
• 输入的所有值均为整数

样例解释 1

以第一个测试用例为例。该输出样例满足所有条件。例如，第 4 个条件可以这样验证：$ P=(2,3,1)\to $（交换 $ P_2,P_3 $）$\to(2,1,3)\to $（交换 $ P_1,P_2 $）$\to(1,2,3) $。反之，下面这种输出是不正确的：

2 1 2 1 3

因为它不满足第 3 个条件。

由 ChatGPT 4.1 翻译