25946번 - Flags 다국어

Consider integer points on the $x$-axis. Every point with an $x$-coordinate of $1$ or greater is associated with one of the colors: red or black. Specifically, as shown in Figure D.1, the color of the point with the $x$-coordinate of $1$ is red, the next two points are black, the next three points are red, the next four points are black, and so on. In this way, every point with an $x$-coordinate of $1$ or greater is associated with either red or black color.

Figure D.1 Colors of points on the $x$-axis

Let $c(x)$ denote the color of the point with coordinate $x$($≥ 1$). Then $c(x)$ is defined as follows.

$$ c(x) = \begin{cases} \text{red,} & \text{if} \displaystyle\sum_{i=0}^{2k}{i} < x \le \displaystyle\sum_{i=0}^{2k+1}{i}&\text{for }k = 0, 1, 2, \dots \\ \text{black,} & \text{otherwise} \end{cases} $$

There are $n$ flags at given points along the $x$-axis. For example, Figure D.2 shows a situation where five flags are erected. The $x$-coordinates of the $n$ flags are denoted as $f_1$, $f_2$, $\dots$, $f_n$.

Figure D.2 An example of five flags on the $x$-axis

Displeased that the colors of points where flags locate are not the same, Bob tries to move all the flags to the right the same distance, say $d$, so that all the flags locate on the red points. In other words, he wants to find $d$ such that for every $i$($1 ≤ i ≤ n$), $c(f_i + d)$ is red.

Given information about the locations of $n$ flags, write a program to find the smallest possible value of $d$.

Your program is to read from standard input. The input starts with a line containing an integer $n$ ($1 ≤ n ≤ 10^5$), where $n$ is the number of flags. Each of the next $n$ lines contains an $x$-coordinate in increasing order. The $i$-th line contains $f_i$ ($1 ≤ i ≤ n$, $1 ≤ f_i ≤ 10^6$), the $x$-coordinate of the $i$-th flag

Your program is to write to standard output. Print exactly one line. The line should contain the minimum distance $d$ by which all the flags must move to the right so that all the flags are on the red points.