你同年幼嘅 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$。下圖展示咗其中一種最優方案：
