You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

均分纸牌

题目描述

有 $n$ 堆纸牌，编号分别为 $1 \sim n$。每堆上有若干张，但纸牌总数必为 $n$ 的倍数。可以在任一堆上取若干张纸牌，然后移动。

移牌规则为：

• 在编号为 1 的堆上取的纸牌，只能移到编号为 2 的堆上；
• 在编号为 $n$ 的堆上取的纸牌，只能移到编号为 $n-1$ 的堆上；
• 其他堆上取的纸牌，可以移到相邻左边或右边的堆上。

现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。

例如 $n=4$，4堆纸牌数分别为 [9, 8, 17, 6]。 移动 3 次可达到目的：

1. 从第2堆取1张移动到第1堆 → [10, 7, 17, 6]
2. 从第3堆取3张移动到第2堆 → [10, 10, 14, 6]
3. 从第3堆取4张移动到第4堆 → [10, 10, 10, 10]

请你首先求出最少的移动次数 $m$，然后输出 $m$ 行代表一个合法方案，每行3个整数 a b c 代表从第 a 堆取 c 张移动到第 b 堆。

在移动过程中始终保证所有数值非负。若有多解输出字典序最小的。

输入格式

• 第一行一个整数 $n$
• 第二行 $n$ 个整数表示每堆的纸牌数量

输出格式

• 第一行输出一个整数 $m$ 代表最小移动次数
• 接下来 $m$ 行，每行3个整数 a b c 代表一次移动
• 你需要保证方案合法。

样例

样例1输入

4

9 8 17 6

样例1输出

3

2 1 1

3 2 3

3 4 4

样例2输入

5

134 10 8 54 4

样例2输出

4

1 2 92

2 3 60

3 4 26

4 5 38

样例3输入

4

0 0 0 4

样例3输出

3

3 2 2

2 1 1

3 4 1

样例4输入

4

0 0 4 0

样例4输出

3

3 2 2

2 1 1

3 4 1

数据范围

• 对于30%的数据，$n \leq 10$
• 对于60%的数据，$n \leq 1000$
• 对于100%的数据，$n \leq 10^5$，保证答案不超过 $2 \times 10^5$

注意：采用快速的输入和输出方式。