有 $n$ 个宝箱排成一行，编号从 $1$ 到 $n$。其中一个宝箱里有宝藏，其余的都是空的。你想找到宝藏，但打开所有的宝箱太耗时了，所以你想确定宝藏所在的宝箱。

你还有 $n$ 个传送器，第 $i$ 个传送器位于第 $i$ 个宝箱上方。你可以激活任意一个传送器，宝藏会被对称地传送到传送器的另一侧。也就是说，如果你激活传送器 $a$，而宝藏位于宝箱 $b$ 中，那么宝藏的新位置将是 $b + (a - b) \cdot 2$。如果存在编号为该数值的宝箱，宝藏就会被传送到该宝箱中。如果不存在编号为该数值的宝箱，宝藏将留在宝箱 $b$ 中，并且你会知道传送未成功。

每个传送器都有自己的使用成本，使用一次传送器 $i$ 需要支付 $c_i$ 的费用。请找出你最少需要花费多少钱，才能在多次使用传送器后确定宝藏的位置。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 500$)，表示宝箱的数量。

第二行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$)，表示每个传送器的使用成本。

输出格式

输出你为了确定宝藏位置所需的最少花费。

样例

输入格式 1

3
5 2 1

输出格式 1

4

说明

在第一个样例中，你可以先激活传送器 3。如果传送成功，那么宝藏只可能在宝箱 3 中。如果传送不成功，你会知道宝藏在宝箱 1 或 2 中。然后你可以激活传送器 2，之后宝藏就会在宝箱 2 或 3 中。此后你可以激活传送器 3，如果传送成功，宝藏就在宝箱 3 中，否则就在宝箱 2 中。

输入格式 2

12
18 19 11 2 20 15 18 1 14 1 1 1

输出格式 2

6