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$ .

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

19C. Swap Threshold

Constraints

Input

Output

Samples

19C. Swap Threshold

Constraints

Input

Output

Samples