|M. Sporyshev, A. Zhikhareva
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.
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.
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.
1 ≤ N ≤ 105
0 ≤ ai ≤ 109
|Input file (
|Output file (