Together with little Kostek, you are building towers out of blocks. You have already built $n$ towers in a row, the $i$-th of height $h_i$. Now Kostek wants to set a boundary between his and your towers. The towers to the left of the boundary will belong to Kostek, and the remaining towers on the right will be yours. Each of you must have at least one tower.

You are about to move on to the next game, which begins with each of you placing a scout on your highest tower. The game won't be fun if the scouts are standing on completely different heights. Therefore, you should suggest the fairest possible division – choose the boundary so as to minimize the absolute value of the difference between the height of Kostek's highest tower and yours. Print this minimal difference.

Input

The first line contains an integer $n$ ($2 \le n \le 300\,000$), denoting the number of towers.

The second line contains $n$ integers $h_1, h_2, \dots, h_n$ ($1 \le h_i \le 10^9$), denoting the heights of consecutive towers from left to right.

Output

Print one integer – the smallest possible difference in height between the tallest of your towers and the tallest of Kostek's towers.

Examples

Input 1

3
200 333 100

Output 1

133

Input 2

5
5 2 4 1 5

Output 2

0

Input 3

6
5 1 4 4 2 3

Output 3

1

Note

In the first test, Kostek should set the boundary between the first two towers. He then has a tower of height $200$, while you have towers of heights $333$ and $100$. Your tallest towers are $200$ and $333$, so the result is $133$. It's not possible to achieve a smaller difference.

In the second test, any division results in a difference of $0$.

In the third test, Kostek should set the boundary after the first, second, or third tower. The required difference is then $|5 - 4| = 1$. The diagram below shows one of these optimal possibilities: