Добро пожаловать в город Иннополис. Весь год бедные жители Иннополиса страдают от постоянного строительства.
Из окна вашей комнаты, вы можете увидеть последовательность из n холмов, где высота i-го из них равна ai. Администрация города Иннополис хочет построить несколько домов на этих холмах. При этом для красоты города было принято решение, что дом может быть построен только на холме, который строго выше соседних холмов (если таковые есть). Например, если последовательность высот это 5, 4, 6, 2, то в этом случае дом может быть построен только на холмах с высотой 5 и 6.
У администрации Иннополиса есть экскаватор, который может уменьшить высоту любого холма на единицу за один час. Экскаватор может работать только над одним холмом одновременно. Разрешено уменьшать высоту холмов до нуля, или даже до отрицательных значений. Увеличение высоты любого холма невозможно. Администрация города хочет построить k домов, поэтому должно быть хотя бы k холмов, которые соотвествуют условию, описанному выше. Какое минимальное количество времени нужно, чтобы осуществить план администрации?
Однако, конкретная величина k до сих пор не определена. Вам предлагается посчитать нужную величину для всех возможных k в отрезке 
. Здесь 
обозначает n делённое на 2, округлённое вверх.
Первая строка ввода состоит из единственного целого n (1 ≤ n ≤ 5000)— количества холмов в последовательности.
Вторая строка содержит n целых чисел ai (1 ≤ ai ≤ 100 000) — высоты холмов в последовательности.
Выведите чисел, разделенных пробелами. i-ое выведенне число должно быть равно минимальному числу часов, необходимому чтобы изменить холмы, так чтобы можно было построить i домов.
5
1 1 1 1 1
1 2 2
3
1 2 3
0 2
5
1 2 3 2 2
0 1 3
В первом примере, чтобы получить хотя бы один холм, пригодный для строительства, можно уменьшить второй холм на один за один час, тогда последовательность станет равной 1, 0, 1, 1, 1 и первый холм будет пригоден для строительства.
В первом примере, чтобы получить хотя бы два или три холма пригодных для строительства, можно уменьшить второй и четвертый холм на один, тогда последовательность станет равной 1, 0, 1, 0, 1 и холмы 1, 3, 5 будут пригодны для строительства.
