题目描述

给定一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$。你可以进行任意次如下操作：

• 选择正整数 $i$ 和整数 $x$，对于所有满足 $i|j$ 的 $j$，$a_j\gets a_j+x$。这次操作的代价为 $|x|$。 求把序列的所有元素变成 $0$ 的最小代价。如果无解，输出 $-1$。

输入

第一行一个正整数 $n$。 第二行 $n$ 个整数，描述序列 $a$。

输出

一行，包含一个整数，表示把序列的所有元素变成 $0$ 的最小代价。如果无解，输出 $-1$。

样例

输入

4
1 -1 0 1

输出

6

数据范围

对于 $20\%$ 的数据，$n\le 5$。

对于 $50\%$ 的数据，$n\le 5\times 10^3$。

对于 $80\%$ 的数据，$n\le 10^5$。 

对于 $100\%$ 的数据，$1\le n\le 10^6$，$|a_i|\le 10^9$。