Problem F. Flasks equalizing

Author:M. Sporyshev, A. Zhikhareva   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

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

Flask number i contains ai 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 ai. 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 ≤ 105

0 ≤ ai ≤ 109

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5
7 7 1 5 5
2
2 0 4
1 0 2
2
5
7 6 1 5 6
4
2 0 3
4 1 0
1 0 2
5 1 0

0.226s 0.112s 13