#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/contests/19/problems/C

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████

Swap Threshold - Repovive Starter Round 6 | Repovive

19C. Swap Threshold

1500 pts1s256 MB

You are given an array $a$ of length $n$ .

Before performing any operations, choose a non-negative integer $k$ . Then, you may perform the following operation any number of times:

Choose an index $i$ with $1 \le i < n$ such that $|a_i-a_{i+1}| \le k$ , and swap $a_i$ with $a_{i+1}$ .

Find the minimum value of $k$ for which it is possible to sort the array in non-decreasing order.

Constraints

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

Input

The input consists of two lines:

n

a_1 \quad a_2 \quad \cdots \quad a_n

Output

Output one integer, the minimum possible value of $k$ .

Samples

Input

4
4 1 3 2

Explanation

With $k=3$ , one possible sequence is

$[4,1,3,2] \rightarrow [1,4,3,2] \rightarrow [1,3,4,2] \rightarrow [1,3,2,4] \rightarrow [1,2,3,4]$ .

A value smaller than $3$ does not allow $4$ and $1$ to swap, although their order must change. Therefore, the minimum value is $3$ .

Output

Input

5
1 2 2 7 9

Explanation

The array is already sorted, so no operation is needed. We may choose $k=0$ .

Output

Input

5
8 4 6 7 5

Explanation

With $k=4$ , the array can be sorted as follows:

$[8,4,6,7,5] \rightarrow [4,8,6,7,5] \rightarrow [4,6,8,7,5] \rightarrow [4,6,7,8,5] \rightarrow [4,6,7,5,8] \rightarrow [4,6,5,7,8] \rightarrow [4,5,6,7,8]$ .

If $k<4$ , the elements $8$ and $4$ cannot swap, so they cannot reach their required order. Thus, the answer is $4$ .

Output

You are given an array $a$ of length $n$ .

Before performing any operations, choose a non-negative integer $k$ . Then, you may perform the following operation any number of times:

Choose an index $i$ with $1 \le i < n$ such that $|a_i-a_{i+1}| \le k$ , and swap $a_i$ with $a_{i+1}$ .

Find the minimum value of $k$ for which it is possible to sort the array in non-decreasing order.

$1 \le n \le 2 \times 10^5$
$1 \le a_i \le 10^9$

The input consists of two lines:

n

a_1 \quad a_2 \quad \cdots \quad a_n

Output one integer, the minimum possible value of $k$ .

With $k=3$ , one possible sequence is

$[4,1,3,2] \rightarrow [1,4,3,2] \rightarrow [1,3,4,2] \rightarrow [1,3,2,4] \rightarrow [1,2,3,4]$ .

A value smaller than $3$ does not allow $4$ and $1$ to swap, although their order must change. Therefore, the minimum value is $3$ .

The array is already sorted, so no operation is needed. We may choose $k=0$ .

With $k=4$ , the array can be sorted as follows:

$[8,4,6,7,5] \rightarrow [4,8,6,7,5] \rightarrow [4,6,8,7,5] \rightarrow [4,6,7,8,5] \rightarrow [4,6,7,5,8] \rightarrow [4,6,5,7,8] \rightarrow [4,5,6,7,8]$ .

If $k<4$ , the elements $8$ and $4$ cannot swap, so they cannot reach their required order. Thus, the answer is $4$ .

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

	#	Title	Points	Solved	Admin

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

Commentary

My submissions

Sponsors

Ranking

19C. Swap Threshold

Constraints

Input

Output

Samples

19C. Swap Threshold

Constraints

Input

Output

Samples