AT_abc432_f.[ABC432F] Candy Redistribution

有 $N$ 个孩子，编号为 $1$ 到 $N$。

第 $i$ 个孩子有 $A_i$ 颗糖果。

你的目标是用尽量少的操作，使得最终所有 $N$ 个孩子分到的糖果数量相同。

每次操作可以：

• 选择两个不同的孩子 $x,y$，再选择一个不超过孩子 $x$ 当前拥有的糖果数的正整数 $z$，从 $x$ 手里拿走 $z$ 颗糖果，给到 $y$。

请判断是否存在一系列操作，使得最终所有 $N$ 个孩子拥有相同数量的糖果。如果存在，请给出一种将操作次数最少的方案。

从标准输入读入，格式如下：

$N$ $A_1$ $\dots$ $A_N$

如果不存在任何一种使所有 $N$ 个孩子分到相同数量糖果的操作方案，输出 -1。

如果存在，请输出操作最少的一种方案，格式如下：

$q$
$x_1$ $y_1$ $z_1$
$\vdots$
$x_q$ $y_q$ $z_q$

其中 $q$ 表示操作次数，$x_i, y_i, z_i$ 分别表示第 $i$ 次操作选择的 $x, y, z$。

如果方案不唯一，输出任意一种都视为正确。

样例解释 1

本样例的操作过程如下：

1. 从第 $2$ 个孩子拿 $1$ 颗糖果，给到第 $3$ 个孩子。此时每个孩子的糖果数为 $1, 6, 5, 8$。
2. 从第 $2$ 个孩子拿 $1$ 颗糖果，给到第 $4$ 个孩子。此时每个孩子的糖果数为 $1, 5, 5, 9$。
3. 从第 $4$ 个孩子拿 $4$ 颗糖果，给到第 $1$ 个孩子。此时每个孩子的糖果数为 $5, 5, 5, 5$。

最终，所有孩子都有 $5$ 颗糖果。

数据范围

• $2 \leq N \leq 20$
• $1 \leq A_i \leq 10^8$
• 所有输入均为整数。

由 ChatGPT 5 翻译