어린 Kostek과 함께 블록으로 탑을 쌓고 있습니다. 이미 일렬로 $n$개의 탑을 쌓았으며, $i$번째 탑의 높이는 $h_i$입니다. 이제 Kostek은 자신의 탑과 여러분의 탑 사이에 경계선을 정하고 싶어 합니다. 경계선 왼쪽의 탑들은 Kostek의 것이 되고, 오른쪽의 나머지 탑들은 여러분의 것이 됩니다. 두 사람 모두 적어도 하나의 탑을 가져야 합니다.

이제 다음 게임으로 넘어가려고 하는데, 이 게임은 각자 자신의 가장 높은 탑 위에 정찰병을 올려놓는 것으로 시작합니다. 정찰병들이 완전히 다른 높이에 서 있으면 게임이 재미없어질 것입니다. 따라서 가능한 한 가장 공평한 분할을 제안해야 합니다. 즉, Kostek의 가장 높은 탑의 높이와 여러분의 가장 높은 탑의 높이 차이의 절댓값이 최소가 되도록 경계선을 선택하세요. 이 최소 차이를 출력하세요.

입력

첫 번째 줄에는 탑의 개수를 나타내는 정수 $n$ ($2 \le n \le 300\,000$)이 주어집니다.

두 번째 줄에는 왼쪽에서 오른쪽으로 연속된 탑들의 높이를 나타내는 $n$개의 정수 $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$)이 주어집니다.

출력

여러분의 가장 높은 탑과 Kostek의 가장 높은 탑 사이의 가능한 최소 높이 차이를 나타내는 정수 하나를 출력합니다.

예제

입력 1

3
200 333 100

출력 1

133

입력 2

5
5 2 4 1 5

출력 2

0

입력 3

6
5 1 4 4 2 3

출력 3

1

노트

첫 번째 테스트에서 Kostek은 처음 두 탑 사이에 경계선을 설정해야 합니다. 그러면 그는 높이 $200$인 탑을 가지게 되고, 여러분은 높이 $333$과 $100$인 탑을 가지게 됩니다. 각자의 가장 높은 탑은 $200$과 $333$이므로 결과는 $133$입니다. 이보다 더 작은 차이를 만드는 것은 불가능합니다.

두 번째 테스트에서는 어떻게 나누더라도 차이가 $0$이 됩니다.

세 번째 테스트에서 Kostek은 첫 번째, 두 번째 또는 세 번째 탑 뒤에 경계선을 설정해야 합니다. 그러면 구하고자 하는 차이는 $|5 - 4| = 1$이 됩니다. 아래 그림은 이러한 최적의 방법 중 하나를 보여줍니다: