Андрей работает судьей на чемпионате по гипершашкам. В каждой игре в гипершашки участвует три игрока. По ходу игры каждый из игроков набирает некоторое положительное целое число баллов. Если после окончания игры первый игрок набрал \(a\) баллов, второй — \(b\), а третий \(c\), то говорят, что игра закончилась со счетом \(a:b:c\).

Андрей знает, что правила игры гипершашек устроены таким образом, что в результате игры баллы любых двух игроков различаются не более чем в \(k\) раз.

После матча Андрей показывает его результат, размещая три карточки с очками игроков на специальном табло. Для этого у него есть набор из n карточек, на которых написаны числа \(x_1, x_2, …, x_n\). Чтобы выяснить, насколько он готов к чемпионату, Андрей хочет понять, сколько различных вариантов счета он сможет показать на табло, используя имеющиеся карточки.

Требуется написать программу, которая по числу \(k\) и значениям чисел на карточках, которые имеются у Андрея, определяет количество различных вариантов счета, которые Андрей может показать на табло.

Цикл лекций в университете Флатландии посвящен изучению последовательностей.

Профессор называет последовательность целых чисел \(a_1, a_2, …, a_n\) гармоничной, если каждое число, кроме \(a_1\) и \(a_n\), равно сумме соседних: \(a_2 = a_1 + a_3, a_3 = a_2 + a_4, …, a_{n-1} = a_{n-2} + a_n\). Например, последовательность \([1, 2, 1, –1]\) является гармоничной, поскольку \(2 = 1 + 1\), и \(1 = 2 + (–1)\).

Рассмотрим последовательности равной длины: \(A = [a_1, a_2, …, a_n]\) и \(B = [b_1, b_2, …, b_n]\). Расстоянием между этими последовательностями будем называть величину \(d(A, B) = |a_1 – b_1| + |a_2 – b_2| + … + |a_n – b_n|\). Например, \(d([1, 2 ,1, –1], [1, 2, 0, 0]) = |1 – 1| + |2 – 2| + |1 – 0| + |–1 – 0| = 0 + 0 + 1 + 1 = 2.\)

В конце лекции профессор написал на доске последовательность из \(n\) целых чисел \(B = [b_1, b_2, …, b_n]\) и попросил студентов в качестве домашнего задания найти гармоничную последовательность \(A = [a_1, a_2, …, a_n]\), такую, что \(d\)(\(A\), \(B\)) минимально. Чтобы облегчить себе проверку, профессор просит написать в качестве ответа только искомое минимальное расстояние \(d(A, B)\).

Требуется написать программу, которая по заданной последовательности \(B\) определяет, на каком минимальном расстоянии от последовательности \(B\) найдется гармоничная последовательность \(A\).