Minimizing Maximum Absolute Value After Uniform Operations

You are given a sequence of n integers \(a_1, a_2, \dots, a_n\). You are allowed to perform an arbitrary number of operations (possibly zero). In each operation, you must choose one of the following two options:

• Global Increment: For every \(1 \le i \le n\), set \(a_i := a_i+1\).
• Global Decrement: For every \(1 \le i \le n\), set \(a_i := a_i-1\).

These operations are equivalent to choosing an integer k (which can be positive, negative, or zero) and replacing every element \(a_i\) with \(a_i+k\). Your goal is to find an integer k such that the following quantity is minimized:

[ \min_{k \in \mathbb{Z}} \max_{1 \le i \le n} \lvert a_i + k \rvert. ]

You only need to output the minimum possible value of (\max_{1\le i\le n} |a_i+k|) after applying your chosen operation.

Hint: If \(L = \min_{1 \le i \le n} a_i\) and \(R = \max_{1 \le i \le n} a_i\), then the answer is \(\lceil (R - L)/2 \rceil\).

inputFormat

The first line contains a single integer \(n\) (the length of the sequence). The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\).

outputFormat

Output one integer: the minimized maximum absolute value after performing the optimal operations.

sample

2
-3 1

2