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 翻译