题目描述

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

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

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

例如 $N=4$ 堆纸牌数分别为 $[9,8,17,6]$。

移动 $3$ 次可达到目的：

• 从第二堆取 $1$ 张移动到第一堆：$[10,7,17,6]$
• 从第三堆取 $3$ 张移动到第二堆：$[10,10,14,6]$
• 从第三堆取 $4$ 张移动到第四堆：$[10,10,10,10]$

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

在移动过程中始终保证所有 $a_i\geq0,d>0$，若有多解输出字典序最小的。

输入格式

第一行一个整数 $N$。

第二行 $N$ 个整数 $a_1 \sim a_N$。

输出格式

第一行输出一个整数 $m$ 代表最小移动次数；

接下来 $m$ 行，每行 $3$ 个整数 $(x,y,d)$ 代表一次移动。

你需要保证方案合法。

样例

4
9 8 17 6

3
2 1 1
3 2 3
3 4 4

5
134 10 8 54 4

4
1 2 92
2 3 60
3 4 26
4 5 38

4
0 0 0 4

3
4 3 3
3 2 2
2 1 1

4
0 0 4 0

3
3 2 2
2 1 1
3 4 1

数据范围

对于 $30\%$ 的数据，$N\le 10$；

对于 $60\%$ 的数据，$N\le 1000$；

对于 $100\%$ 的数据，保证 $1 \leq a_i, N \leq 3 \times 10^5$，$\sum a_i$ 是 $N$ 的倍数。

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