← 返回题目列表

Codeforces · 1733/C

C. 奇偶校验随机排序

中文机器翻译题面 查看原题

给定一个数组 $$$a$$$,其中包含 $$$n$$$ 非负整数。您可以对其应用以下操作。

- 选择两个索引 $$$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$$$)。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
2
7 8
5
1 1000000000 3 0 5
1
0

输出 #1

0
2
3 4
1 2
0

注意

在第二个测试用例中,$$$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$$$ 已经是非递减的。