Problem Description

Xiao R is a girl who loves shopping and lives in the country of Ouaie.

Ouaie has \( n \) types of coins with denominations \( 1 = a_1 < a_2 < a_3 < \cdots < a_n \), and it satisfies that \( a_{i+1} \) is a multiple of \( a_i \). In Ouaie, only coins are used for payment.

Stores in Ouaie do not provide change, so she must pay the exact price with coins. For the same price, there can be different ways of payment. For example, if the denominations of the coins in Ouaie are 1 yuan and 5 yuan, there are two ways to pay 7 yuan: pay 7 one-yuan coins, or pay 1 five-yuan coin and 2 one-yuan coins.

Since the quality of the coins is roughly the same, she does not want to carry too many coins, so she always carries the minimum number of coins required for the purchase. She has noticed a magical phenomenon: sometimes, buying a product that costs 1 yuan more can reduce the number of coins she needs to carry significantly.

Can you find the smallest \( m \) such that the number of coins needed to buy a product costing \( m \) yuan is less than the number of coins needed to buy a product costing \( m-1 \) yuan?

Input Format

The first line contains an integer \( n \), representing the number of coin denominations.

The second line contains \( n \) integers, where the \( i \)-th integer \( a_i \) represents the denomination of the \( i \)-th coin.

Output Format

A single line containing an integer \( m \), representing the answer. If no such \( m \) exists, output \(-1\).

Sample Input and Output

Sample Input #1

4
1 6 12 48

Sample Output #1

6

Sample Input #2

3
1 2 8

Sample Output #2

8

Sample Input #3

1
1

Sample Output #3

-1

Notes

Sample Explanation

For Sample #1, buying products costing from 1 to 5 yuan requires 1 to 5 one-yuan coins, respectively, while buying a product costing 6 yuan only requires 1 six-yuan coin.

For Sample #2, buying a product costing 1 or 2 yuan both require 1 coin, which does not meet the requirement of needing fewer coins.

Data Range

For 100% of the data, \( 1 \le n \le 10 \), \( 1 = a_1 < a_2 < a_3 < \cdots < a_n \le 10^9 \), and it is guaranteed that \( a_{i+1} \) is a multiple of \( a_i \).

Hint: This problem has bundled tests.

This problem consists of 4 subtasks.

Problem Source

见题面 Input 部分

见题面 Output 部分