Problem Description

On a table, there are $ N $ cards arranged in a single row (where $ N $ is an odd number). Each card has a positive integer written on it, and the integer on the $ i $ -th card from the left ( $1 \leq i \leq N$ ) is $ a_i $ . No two different cards have the same integer written on them. The cards are arranged from left to right in ascending order of the integers written on them.

Snuke and Iroha will take turns performing the following operation until there are only 2 cards left on the table, with Snuke going first.

Operation: Choose one card from the cards currently on the table and completely remove it.

When all operations are finished, the absolute difference between the integers written on the remaining two cards will be the score of the game.

There are additional rules for both the first and second players:

• Snuke, the first player, must always choose the card in the middle when it's his turn. That is, if there are $ r $ cards left, he must remove the $ (r+1)/2 $ -th card from the left.
• Iroha, the second player, must choose either the leftmost or the rightmost card from the remaining cards when it's her turn.

Determine the score of the game when Iroha plays optimally to minimize the score.

Input Format

The input is given from the standard input in the following format:

$ N $ $a_1\ a_2\ \cdots\ a_N$

Output Format

Output the score of the game in one line.

Sample Input and Output

Sample Input #1

3
1 5 100

Sample Output #1

99

Sample Input #2

9
3 14 15 20 33 51 59 62 68

Sample Output #2

45

Notes/Hints

Constraints

• $ N $ is an odd number, $a_i\ (1 \leq i \leq N)$ are integers
• $3 \leq N \leq 10^{5}$
• $1 \leq a_i \leq 10^{9}\ (1 \leq i \leq N)$

Sample Explanation 1

Snuke removes the 2nd card from the left, ending the game.

见题面 Input 部分

见题面 Output 部分