给你 $$$n$$$ 整数对 $$$(a_1, b_1), (a_2, b_2), \ldots, (a_n, b_n)$$$。这些对中的所有整数都是不同的,并且范围在 $$$1$$$ 到 $$$2 \cdot n$$$ 之间(包括 $$$1$$$)。
让我们调用整数序列 $$$x_1, x_2, \ldots, x_{2k}$$$ 好,如果
- $$$x_1 < x_2 > x_3 < \ldots < x_{2k-2} > x_{2k-1} < x_{2k}$$$,或
- $$$x_1 > x_2 < x_3 > \ldots > x_{2k-2} < x_{2k-1} > x_{2k}$$$。
您需要选择不同索引 $$$i_1, i_2, \ldots, i_t$$$ 的子集及其顺序,如果您在单个序列中写下这些对中的所有数字(序列将为 $$$a_{i_1}, b_{i_1}, a_{i_2}, b_{i_2}, \ldots, a_{i_t}, b_{i_t}$$$),这个序列很好。
您可以选择的最大索引子集是什么?还需要构造相应的索引序列$$$i_1, i_2, \ldots, i_t$$$。
输入
第一行包含单个整数 $$$n$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$) — 对的数量。
接下来的 $$$n$$$ 行包含两个数字 — $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 2 \cdot n$$$) — 成对的元素。
保证对中的所有整数都是不同的,也就是说,从 $$$1$$$ 到 $$$2 \cdot n$$$ 的每个整数都被恰好提到一次。
输出
在第一行中打印一个整数 $$$t$$$ — 答案中的对数。
然后打印 $$$t$$$ 不同的整数 $$$i_1, i_2, \ldots, i_t$$$ - 按相应顺序的对的索引。
示例
输入 #1
5 1 7 6 4 2 10 9 8 3 5
输出 #1
3 1 5 3
输入 #2
3 5 4 3 2 6 1
输出 #2
3 3 2 1
注意
第一个示例中的最终序列是 $$$1 < 7 > 3 < 5 > 2 < 10$$$。
第二个示例中的最终序列是 $$$6 > 1 < 3 > 2 < 5 > 4$$$。