Решение задачи Минимальная сложность с Codeforces

Миша пытается заниматься скалолазанием, но получается у него из рук вон плохо.

На стене висят n зацепок, i-я из которых расположена на высоте a i от земли. Кроме того, пусть последовательность a i возрастает, т.е. a i < a i + 1 для всех i от 1 до n - 1; назовем такую последовательность трассой. Миша считает, что трасса a 1, ..., a n обладает сложностью . Иными словами, сложность равна максимальному расстоянию между соседними по высоте зацепками.

Сегодня Миша решил пролезть трассу, в которой зацепки висят на высотах a 1, ..., a n. Чтобы усложнить себе задачу, Миша решил снять одну из зацепок, т.е. удалить один элемент последовательности (например, если из последовательности (1, 2, 3, 4, 5) удалить третий элемент, останется последовательность (1, 2, 4, 5)). Однако, поскольку лазает Миша плохо, он хочет, чтобы после удаления сложность (т. е. максимальная разность высоты между соседними зацепками) была минимальной среди всех возможных вариантов снять одну зацепку. Первая и последняя зацепка должны остаться на месте.

Помогите Мише определить минимальную сложность трассы после снятия одной зацепки.