The Less Coins Paradox

Little R is a girl who loves shopping in OA Country. In OA Country there are \(n\) types of coins with denominations \(1 = a_1 < a_2 < a_3 < \cdots < a_n\), and it is guaranteed that for each \(1 \le i < n\), \(a_{i+1}\) is a multiple of \(a_i\). There is only one way of making payments using coins, and the stores do not provide change. That is, when making a purchase, the amount must be paid exactly using a combination of coins.

For the same price, there can be multiple ways to pay. For instance, if the available coins are \(1\) and \(5\), then there are two ways to pay \(7\): using seven \(1\)-coins or one \(5\)-coin plus two \(1\)-coins.

Since all coins have roughly the same weight, Little R wants to carry as few coins as possible. She always pays with the minimum number of coins required. Surprisingly, she observes that sometimes buying a product that costs one unit more can require fewer coins than buying a product that costs one unit less.

Your task is to find the smallest integer \(m\) (with \(m \ge 2\)) such that the minimum number of coins required to pay \(m\) is strictly less than that required for \(m-1\), i.e.: \[ f(m) < f(m-1), \] where \(f(x)\) denotes the minimal number of coins needed to pay \(x\) using a greedy algorithm (which is optimal under the given conditions).

inputFormat

The first line contains a single integer \(n\) (the number of coin types). The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) representing the coin denominations. It is guaranteed that \(a_1 = 1\), \(a_1 < a_2 < \cdots < a_n\), and for every \(1 \le i < n\), \(a_{i+1}\) is a multiple of \(a_i\).

outputFormat

Output the smallest integer \(m\) such that the minimal coins required for \(m\) is less than that for \(m-1\).

sample

2
1 5

10