Problem F. Flasks equalizing ≡

Statement

In the laboratory there is a weird construction consisting of N equal cylindrical flasks in a row.

Flask number i contains a_i milliliters of a liquid.

In a single step, you can pour any amount of liquid from a single flask to one or both its neighbours on the left and on the right in any proportion. The amount of liquid in each flask must remain integer value after each step.

Your program must perform the minimum number of aforementioned steps to make all flasks contain the equal amount of liquid.

Input file format

The first line of the input file contains an integer N.

The second line contains N integers a_i. It is guaranteed that the total amount of liquid is divisible by N.

Output file format

The first line of the output file must contain an integer S — the minimum number of steps.

Each of the following S lines contain three integers I, L, R — the index of the flask starting from 1, the amount of liquid to pour into the flask to the left and the amount of liquid to pour into the flask to the right respectively.

If there are several solutions, output any of them.

Constraints

1 ≤ N ≤ 10⁵

0 ≤ a_i ≤ 10⁹

Sample tests

5
7 7 1 5 5

2
2 0 4
1 0 2

5
7 6 1 5 6

4
2 0 3
4 1 0
1 0 2
5 1 0