Задача F. Flasks equalizing

Автор:M. Sporyshev, A. Zhikhareva   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

В лаборатории стоит необычная конструкция из N одинаковых цилиндрических сосудов, выстроенных в ряд.

В i-й сосуд налито ai миллилитров жидкости.

За один шаг можно перелить любое количество жидкости из одного сосуда в одного или обоих его соседей слева и справа в любой пропорции. Количество жидкости во всех сосудах после каждого шага должно оставаться целочисленным.

Требуется написать программу, выполняющую минимально необходимое количество вышеописанных шагов, чтобы уравнять количество жидкости во всех сосудах.

Формат входного файла

Первая строка входного файла содержит целое число N.

Вторая строка содержит N целых чисел ai. Гарантируется, что общее количество жидкости делится на N.

Формат выходного файла

Первая строка выходного файла должна содержать целое число S — минимальное число шагов.

Следующие S строк содержат по три целых числа I, L, R — индекс сосуда, начиная с 1, увеличение уровня в соседнем слева сосуде, увеличение уровня в соседнем справа сосуде соответственно.

Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 105

0 ≤ ai ≤ 109

Примеры тестов

Входной файл (input.txt) Выходной файл (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.080s 0.017s 15