가장 높은 언덕

스웨덴은 노르웨이나 아이슬란드 같은 다른 NCPC 회원국에 비해 산맥이 그리 인상적이지 않지만, 덴마크의 평지보다는 낫다. 다른 회원국끼리 비교하면 상황이 그리 분명하지 않다. 예를 들어 에스토니아가 리투아니아보다 산이 많은가? 이 질문에 답하려면 두 나라 중 어느 나라가 더 인상적인 산봉우리를 가졌는지 알아내야 한다.

산맥은 $n$개의 등간격 지점에서 높이 $h_i$를 샘플링하여 정의된다. 산맥에서 인덱스의 삼중항 $1 \le i < j < k \le n$이 $h_i \le \cdots \le h_j \ge \cdots \ge h_k$를 만족하면 이를 봉우리라고 부른다. 봉우리의 높이는 $h_j - h_i$와 $h_j - h_k$ 중 작은 값으로 정의한다.

주어진 산맥에서 가장 높은 봉우리의 높이를 구할 수 있는가?

첫 줄에 정수 $N$($3 \le n \le 200\,000$)이 주어진다. 이는 산맥에서 샘플링한 지점의 개수이다.

둘째 줄, 즉 마지막 줄에는 샘플링한 지점들의 높이 $h_1, \dots, h_N$($0 \le h_i \le 318 \cdot 10^9$)이 해수면 기준으로 나노미터 단위로 주어진다.

산맥에는 봉우리가 적어도 하나 있음이 보장된다.

가장 높은 봉우리의 높이를 나타내는 정수 하나를 출력한다.