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