E. Жадный выбор
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
стандартный ввод
вывод
стандартный вывод

Вася занимается исследованием применения жадных алгоритмов в различных областях. Сейчас он пытается изучить применимость жадного алгоритма для задачи о сдаче. Имеется набор из n различных номиналов монет, причем монет каждого номинала имеется неограниченное количество. Задача состоит в том, чтобы набрать сумму x наименьшим числом монет. Жадный алгоритм на каждом шаге берет монету наибольшего номинала, не превосходящего x. Очевидно, что если в наборе номиналов присутствует 1, то любую сумму x можно набрать жадным алгоритмом. Однако жадный алгоритм не всегда даст оптимальное представление данной суммы, т.е. представление, содержащее наименьшее количество монет. К примеру, если имеются номиналы {1, 3, 4} и требуется набрать сумму 6, то жадный алгоритм построит представление 4 + 1 + 1, в то время как оптимальным является представление 3 + 3, содержащее на монету меньше. По заданному набору номиналов определите, существует ли такая сумма x, которую жадный алгоритм наберет неоптимальным способом. Если такая сумма существует, то найдите наименьшую из таких сумм.

Входные данные

Первая строка содержит целое число n (1 ≤ n ≤ 400) — число номиналов монет. Вторая строка содержит n целых чисел ai (1 ≤ ai ≤ 109), задающих номиналы монет. Гарантируется, что a1 > a2 > ... > an и an = 1.

Выходные данные

Если жадный алгоритм набирает любую сумму оптимальным образом, то выведите -1. Иначе выведите наименьшее число, которое жадный алгоритм наберет неоптимальным способом.

Примеры
Входные данные
5
25 10 5 2 1
Выходные данные
-1
Входные данные
3
4 3 1
Выходные данные
6