你和年幼的 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$。下圖展示了其中一種最佳方案：
