Задача C. Уровень столбов

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

Условие

Строительная компания построила кирпичный забор, имеющий N столбов. Из-за недосмотра оказалось, что столбы имеют разную высоту — i-й столб состоит из ai кирпичей, лежащих вертикально один на другом. До приезда проверяющей комиссии осталось совсем немного времени, и за это время строители успеют положить либо убрать не более k кирпичей.

Требуется определить последовательность действий, в результате которой образуется как можно более длинный участок подряд идущих столбов одинаковой высоты — чтобы именно этот участок показать комиссии.

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

Во входном файле находятся числа N k, за которыми следуют N чисел ai.

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

В выходной файл следует вывести числа s e m, где s, e — начало и конец максимального участка (1 ≤ s ≤ e ≤ N), m — количество потребовавшихся действий (0 ≤ m ≤ k). Затем вывести m чисел, di, которые обозначают, что на столб a|di| следует положить кирпич, если di > 0, либо снять кирпич, если di < 0.

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

Ограничения

1 ≤ N ≤ 100, 0 ≤ k, ai ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 2
1 2 3
1 3 2
1 -3
2
4 10
1 5 1 100
1 3 4
-2 -2 -2 -2

0.074s 0.044s 15