Задача с зарубежных стажировок.

Дается массив неотрицательных целых чисел а.
Определим стоимость массива как max(|a0-a1|, |a1-a2|, …..|a[n-2]-a[n-1]|)
Так же вам дают целое неотрицательное число max_value. Вы можете выбрать число х, 0<=х<=max_value и заменить нули из массива а на х.
Ваша задача определить число х таким образом, чтобы стоимость массива после изменения была минимальной.

Решение:
Давайте найдем максимальное и минимальное положительное число которое соседствует с нулем из массива a. Пусть эти числа mx, mn соответственно.
Тогда ответом будет min( (mx+mn)//2, max_value)
Время работы O(N)