给定 $n = 2^k$ 个复数 $a_0, \dots, a_{n-1}$，其离散傅里叶变换 $x_0, \dots, x_{n-1}$ 定义如下：

$$x_k = \sum_{j=0}^{n-1} a_j \cdot e^{-i \cdot 2\pi \cdot jk/n}$$

给定 $n$ 个整数 $a_0, \dots, a_{n-1}$。请构造 $n$ 个实数 $b_0, \dots, b_{n-1}$，使得它们的傅里叶变换的所有值均为实数（即虚部为零），并使总差值 $\sum_{i=0}^{n-1} |a_i - b_i|$ 尽可能小。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2^{20}$，$n$ 是 2 的幂)。第二行包含 $n$ 个空格分隔的整数 $a_0, \dots, a_{n-1}$ ($|a_i| \le 10^9$)。

输出格式

输出一个实数：最小可达到的总差值。如果你的答案与正确答案的绝对误差或相对误差不超过 $10^{-9}$，则会被接受。

样例

样例输入 1

4
1 2 3 4

样例输出 1

2.000000000