CF1733C Parity Shuffle Sorting

给定一个包含 $n$ 个非负整数的数组 $a$。你可以对其进行如下操作： - 选择两个下标 $l$ 和 $r$（$1 \le l < r \le n$）。 - 如果 $a_l + a_r$ 是奇数，则执行 $a_r := a_l$。如果 $a_l + a_r$ 是偶数，则执行 $a_l := a_r$。 请找出最多不超过 $n$ 次操作的任意一种方案，使得数组 $a$ 变为非递减数组。可以证明总是存在可行解。注意，你不需要使操作次数最少。 一个数组 $a_1, a_2, \ldots, a_n$ 是非递减的，当且仅当 $a_1 \le a_2 \le \ldots \le a_n$。

第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。 每个测试用例包含两行。第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示数组本身。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，第一行输出一个整数 $m$（$0 \le m \le n$），表示操作次数。 接下来 $m$ 行，每行输出两个整数 $l_i, r_i$，表示你在第 $i$ 次操作中选择的下标（$1 \le l_i < r_i \le n$）。 如果有多种方案，输出任意一种均可。

在第二个测试用例中，$a$ 的变化如下： - 选择下标 $3$ 和 $4$，$a_3 + a_4 = 3$ 是奇数，因此执行 $a_4 := a_3$。此时 $a = [1, 1000000000, 3, 3, 5]$。 - 选择下标 $1$ 和 $2$，$a_1 + a_2 = 1000000001$ 是奇数，因此执行 $a_2 := a_1$。此时 $a = [1, 1, 3, 3, 5]$，数组已非递减。 在第一个和第三个测试用例中，$a$ 已经是非递减的。 由 ChatGPT 4.1 翻译