题目描述

小 R 是一个喜欢购物的女孩子，她生活在欧艾国中。

欧艾国共有 $n$ 种面值的硬币，它们的面值分别为 $1=a_1 < a_2 < a_3 < \cdots < a_n$，且满足 $a_{i+1}$ 是 $a_i$ 的倍数。欧艾国只有硬币一种付款方式。

欧艾国的商店不支持找零，她在购物时必须支付与价格完全相等的硬币。对于同样的价格，可以有不同的支付方式。例如，如果欧艾国硬币的面值为 $1$ 元和 $5$ 元，那么支付 $7$ 元有两种方式：支付 $7$ 枚 $1$ 元硬币，或者支付 $1$ 枚 $5$ 元硬币和 $2$ 枚 $1$ 元硬币。

由于硬币的质量大致相同，她不希望携带的硬币太重，因此每次购物都会携带符合要求的尽量少的硬币。她发现了一个神奇的现象：有的时候多买 $1$ 元的商品可以使她少带很多硬币。

你能求出最小的 $m$，使得买 $m$ 元的商品需要的硬币数比买 $m-1$ 元的商品需要的硬币数更少吗？

输入格式

第一行一个整数 $n$，表示硬币面值数。

第二行 $n$ 个整数，第 $i$ 个为 $a_i$，表示第 $i$ 种硬币的面值。

输出格式

一行，一个整数 $m$，表示答案。特别地，如果不存在这样的 $m$，请输出 $-1$。

4
1 6 12 48

6

3
1 2 8

8

1
1

-1

提示

样例解释

对于样例 $1$，购买 $1\sim 5$ 元的商品分别需要 $1\sim 5$ 枚 $1$ 元硬币，购买 $6$ 元的商品只需要 $1$ 枚 $6$ 元硬币。

对于样例 $2$，购买 $1$ 元或 $2$ 元的商品都需要 $1$ 枚硬币，并不满足需要的硬币数更少的要求。

数据范围

对于 $100\%$ 的数据，$1\le n\le 10$，$1=a_1 < a_2 < a_3 < \cdots < a_n\le 10^9$，且满足 $a_{i+1}$ 是 $a_i$ 的倍数。

提示：本题开启捆绑测试。

本题共 $4$ 个子任务。

题目来源