Background

A huge repulsive force strikes. Your whole body seems to split into transparent fragments.

In the mirror there is a blurry figure. Is it “you”? Or is it just an illusion? There is no way to know. You want to move forward, but the other side retreats with extreme coordination. When you step back, the other side catches up again.

There is no energy left to support you to keep thinking. But toward that faint light source in the center of the prism, no matter what, you want to get a little closer. Also, there is the other “you” on the opposite side......

Problem Description

Given an integer sequence $a_1,\ldots,a_n$ of length $n$. You may perform any number of operations (including zero). In each operation, you must choose one of the following two types:

• Global increment by $1$: for every $1 \leq i \leq n$, increment $a_i$ by $1$.
• Global decrement by $1$: for every $1 \leq i \leq n$, decrement $a_i$ by $1$.

You want to minimize $\max\limits_{i=1}^n \lvert a_i \rvert$ after the operations, i.e., minimize the maximum value among all $\lvert a_i\rvert$, where $\lvert a_i\rvert$ denotes the absolute value of $a_i$. You only need to compute this minimized value.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers $a_1,\ldots,a_n$, describing the given sequence.

Output Format

Output one line containing one integer, the minimum possible value of $\max\limits_{i=1}^n \lvert a_i \rvert$.

5
-5 -2 0 2 3

4

6
1 -1 4 5 -1 4

3

18
9 9 8 2 4 4 3 5 3 0 9 0 2 2 8 1 1 5

5

Hint

Sample Explanation #1.

You only need to apply one global increment by $1$ to obtain $a = [-4, -1, 1, 3, 4]$. Then $\lvert a_1 \rvert, \lvert a_2 \rvert, \lvert a_3 \rvert, \lvert a_4 \rvert, \lvert a_5 \rvert$ are $4, 1, 1, 3, 4$ respectively, and the maximum is $4$. It can be proven that $4$ is the minimum value you can achieve.

Constraints.

• Special Property A: $n$ is guaranteed to be even, and for every integer $k$ satisfying $1 \leq k \leq \frac n2$, $a_{2k-1} = -a_{2k}$.
• Special Property B: $a_i \geq 0$ is guaranteed.

For $100\%$ of the testdata, it is guaranteed that $1 \leq n \leq 100$ and $-10^9 \leq a_i \leq 10^9$.

Translated by ChatGPT 5