在 Softville 村庄里，人们习惯以一种特殊的方式来编写软件：在第一天，程序员会写若干行代码（至少一行），此后的每一天，他/她写代码的行数都比前一天恰好增加一行。

在满 10 岁之后，Softville 的每位居民都必须通过从头编写一个非常复杂的程序来接受启蒙。该程序的代码对所有居民都是相同的，且恰好包含 $N$ 行。每位居民完成这项任务所花费的天数可能不同。然而，规则始终适用：每天每位程序员写代码的行数都比前一天多一行。

你将获得关于 Softville 居民编写该启蒙程序所花费天数的数据。你需要确定 $N$（即程序的行数）的最小可能值。

输入格式

输入的第一行包含一个整数 $m$（$0 \le m \le 1000$），表示 Softville 居民的人数。

第二行包含 $m$ 个数字，表示每位居民编写该启蒙程序所花费的天数。第二行中的所有数字均为正整数，且小于 $2^{63}$。

输出格式

输出中唯一的数字应当是 $N$ 的最小可能值。如果无论 $N$ 取何值，输入数据都无法保持一致，则应输出 0；否则，保证 $N$ 的最小可能值小于 $2^{63}$。

样例

输入样例 1

2
2 3

输出样例 1

9

输入样例 2

2
4 2

输出样例 2

0