Minimum Maximum Absolute Difference in a Circular Arrangement

You are given a permutation of the integers from 1 to n representing the heights of n children. Your task is to arrange the children in a circle so that the maximum absolute difference between the heights of any two neighboring children is minimized.

More formally, let the heights be given as a sequence \(h_1, h_2, \dots, h_n\) (a permutation of \(\{1, 2, \dots, n\}\)). You need to determine an arrangement (i.e., a circular permutation) such that the value

[ D = \max_{1 \le i \le n} |a_{i+1} - a_i| ]

is minimized (here, we take (a_{n+1} = a_1) because the arrangement is circular). Output the minimal possible value of (D>.

Note: You are guaranteed that each test case consists of a permutation of \(\{1,2,\dots,n\}\>.

inputFormat

The input is given via standard input (stdin) and has the following format:

• The first line contains a single integer \(n\) representing the number of children.
• The second line contains \(n\) space-separated integers representing the unique heights of the children.

You can assume that the provided heights form a permutation of \(\{1, 2, \dots, n\}\>.

outputFormat

Output a single integer which is the minimal possible maximum absolute difference between the heights of any two consecutive children in an optimal circular arrangement. The output should be written to standard output (stdout).

5
4 1 3 2 5

1