CF10E.Greedy Change

Billy investigates the question of applying greedy algorithm to different spheres of life. At the moment he is studying the application of greedy algorithm to the problem about change. There is an amount of n coins of different face values, and the coins of each value are not limited in number. The task is to collect the sum x with the minimum amount of coins. Greedy algorithm with each its step takes the coin of the highest face value, not exceeding x. Obviously, if among the coins' face values exists the face value 1, any sum x can be collected with the help of greedy algorithm. However, greedy algorithm does not always give the optimal representation of the sum, i.e. the representation with the minimum amount of coins. For example, if there are face values {1, 3, 4} and it is asked to collect the sum 6, greedy algorithm will represent the sum as 4 + 1 + 1, while the optimal representation is 3 + 3, containing one coin less. By the given set of face values find out if there exist such a sum x that greedy algorithm will collect in a non-optimal way. If such a sum exists, find out the smallest of these sums.

比利正在研究贪心算法在不同生活领域中的应用。目前，他正在研究贪心算法在找零问题中的应用。现有 $n$ 种面值的硬币，且每种面值的硬币数量无限。任务是用最少数量的硬币凑出总和 $x$。贪心算法在每一步中都选取不超过当前剩余金额 $x$ 的最大面值硬币。显然，若硬币面值集合中包含面值 $1$，则任意总和 $x$ 均可通过贪心算法凑出。然而，贪心算法并不总能给出最优的凑法（即所需硬币数量最少的表示）。例如，当硬币面值为 $\{1,\,3,\,4\}$ 且需凑出总和 $6$ 时，贪心算法会给出表示 $4 + 1 + 1$，而最优表示为 $3 + 3$，后者少用一枚硬币。给定一组硬币面值，请判断是否存在某个总和 $x$，使得贪心算法给出的表示非最优；若存在，求出满足条件的最小总和 $x$。

The first line contains an integer n (1 ≤ n ≤ 400) — the amount of the coins' face values. The second line contains n integers a__i (1 ≤ a__i ≤ 109), describing the face values. It is guaranteed that _a_1 > _a_2 > ... > a__n and a__n = 1.

第一行包含一个整数 $n$（$1 \leq n \leq 400$）—— 表示硬币面值的种类数。
第二行包含 $n$ 个整数 $a_i$（$1 \leq a_i \leq 10^9$），描述各个硬币的面值。
保证 $a_1 > a_2 > \dots > a_n$ 且 $a_n = 1$。

If greedy algorithm collects any sum in an optimal way, output -1. Otherwise output the smallest sum that greedy algorithm collects in a non-optimal way.

如果贪心算法能以最优方式收集任意和，则输出 -1；否则输出贪心算法以非最优方式收集的最小和。