Wesley 收到了一個包含 $N$ 個元素的陣列 $(a_1, a_2, \dots, a_N)$ 作為復活節禮物，他非常渴望將其排序（使得 $a_1 \le a_2 \le \dots \le a_N$）。

感到無聊的 Wesley 決定增加挑戰難度，他規定自己只有在兩個元素的絕對差小於或等於 $K$ 時，才能交換這兩個元素。請注意，這些元素可以在陣列中的任何位置；只要它們的絕對差小於或等於 $K$，Wesley 就可以交換它們。

不幸的是，Wesley 很快意識到這可能無法將陣列排序。他接著感到好奇：為了能夠將陣列排序，所需的 $K$ 之最小值是多少？

輸入格式

第一行包含一個整數 $N$，代表陣列中的元素數量 $(1 \le N \le 2 \cdot 10^5)$。

下一行包含 $N$ 個整數 $a_1, a_2, \dots, a_N$，即陣列本身 $(1 \le a_i \le 10^{18})$。

輸出格式

輸出為了能夠將陣列排序所需的 $K$ 之最小值。如果陣列已經排序完成，則應輸出 0。

範例

輸入 1

8
1 4 4 2 7 14 12 10

輸出 1

2