← 返回题目列表

Codeforces · 1144/D

D. 均衡它们

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

给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。您可以执行任意次数的以下操作(可能为零):

1. 选择一对索引 $$$(i, j)$$$,使得 $$$|i-j|=1$$$ (索引 $$$i$$$ 和 $$$j$$$ 相邻)并设置 $$$a_i := a_i + |a_i - a_j|$$$;
2. 选择一对索引 $$$(i, j)$$$,使得 $$$|i-j|=1$$$(索引 $$$i$$$ 和 $$$j$$$ 相邻)并设置 $$$a_i := a_i - |a_i - a_j|$$$。

值 $$$|x|$$$ 表示 $$$x$$$ 的绝对值。例如,$$$|4| = 4$$$, $$$|-3| = 3$$$。

您的任务是找到获得相等元素的数组所需的最少操作数并打印操作顺序。

使用此类操作保证您始终可以获得相等元素的数组。

请注意,每次操作后当前数组的每个元素的绝对值不应超过 $$$10^{18}$$$。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — $$$a$$$ 中的元素数量。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 2 \cdot 10^5$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。

输出

在第一行打印一个整数 $$$k$$$ — 获得相等元素的数组所需的最少操作数。

在接下来的 $$$k$$$ 行中打印操作本身。第 $$$p$$$ 操作应打印为整数三元组 $$$(t_p, i_p, j_p)$$$,其中 $$$t_p$$$ 是 $$$1$$$ 或 $$$2$$$($$$1$$$ 表示执行第一种类型的操作,$$$2$$$ 表示执行第二种类型的操作),并且 $$$i_p$$$ 和$$$j_p$$$ 是数组相邻元素的索引,使得 $$$1 \le i_p, j_p \le n$$$, $$$|i_p - j_p| = 1$$$。请参阅示例以更好地理解。

请注意,每次操作后当前数组的每个元素的绝对值不应超过 $$$10^{18}$$$。

如果有很多可能的答案,您可以打印任何一个。

示例

输入 #1

5
2 4 6 6 6

输出 #1

2
1 2 3 
1 1 2

输入 #2

3
2 8 10

输出 #2

2
2 2 1 
2 3 2

输入 #3

4
1 1 1 1

输出 #3

0