CF496A Minimum Difficulty

Mike is trying rock climbing but he is awful at it. There are $ n $ holds on the wall, $ i $ -th hold is at height $ a_{i} $ off the ground. Besides, let the sequence $ a_{i} $ increase, that is, $ a_{i}

Mike is trying rock climbing but he is awful at it. There are $ n $ holds on the wall, $ i $ -th hold is at height $ a_{i} $ off the ground. Besides, let the sequence $ a_{i} $ increase, that is, $ a_{i}

Print a single number — the minimum difficulty of the track after removing a single hold.

In the first sample you can remove only the second hold, then the sequence looks like $ (1,6) $ , the maximum difference of the neighboring elements equals 5. In the second test after removing every hold the difficulty equals 2. In the third test you can obtain sequences $ (1,3,7,8) $ , $ (1,2,7,8) $ , $ (1,2,3,8) $ , for which the difficulty is 4, 5 and 5, respectively. Thus, after removing the second element we obtain the optimal answer — 4.