원형 수열 줄이기

서로 다른 양의 정수로 이루어진 길이 $N$의 원형 수열 $A$가 있다. 원형 수열에서 $A_N$의 다음 원소는 $A_1$이다.

현재 수열에 원소가 세 개 이상 남아 있을 때 다음 연산을 할 수 있다.

• 양옆에 있는 두 원소보다 모두 크거나, 양옆에 있는 두 원소보다 모두 작은 원소 하나를 선택하여 제거한다.

원소를 제거하면 제거한 원소의 양옆에 있던 두 원소가 서로 이웃하게 된다.

원소가 두 개 남을 때까지 연산을 반복할 때, 마지막에 남은 두 원소의 차의 최댓값을 구하여라.

첫 번째 줄에 수열의 길이를 의미하는 정수 $N$이 주어진다. $(3 \leq N \leq 200\,000)$

두 번째 줄에 수열의 원소를 의미하는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(1 \leq A_i \leq 10^9)$

모든 $A_i$는 서로 다르다.

첫 번째 줄에 마지막에 남은 두 원소의 차의 최댓값을 출력한다.