P9412 "NnOI R1-T1" Shopping

Little R is a girl who likes shopping. She lives in the country OAI. There are $n$ kinds of coin denominations in OAI. Their values are $1=a_1 < a_2 < a_3 < \cdots < a_n$, and they satisfy that $a_{i+1}$ is a multiple of $a_i$. In OAI, the only payment method is coins. Shops in OAI do not support making change. When she shops, she must pay with coins whose total value is exactly equal to the price. For the same price, there can be different payment methods. For example, if the coin denominations in OAI are $1$ yuan and $5$ yuan, then paying $7$ yuan has two methods: pay $7$ coins of $1$ yuan, or pay $1$ coin of $5$ yuan and $2$ coins of $1$ yuan. Since the coins have roughly the same weight, she does not want to carry coins that are too heavy, so for each purchase she will carry as few coins as possible while meeting the requirement. She discovered a magical phenomenon: sometimes buying an item that costs $1$ yuan more can make her carry many fewer coins. Can you find the smallest $m$ such that buying an item costing $m$ yuan requires fewer coins than buying an item costing $m-1$ yuan?

The first line contains an integer $n$, indicating the number of coin denominations. The second line contains $n$ integers. The $i$-th integer is $a_i$, indicating the value of the $i$-th coin denomination.

One line containing one integer $m$, which is the answer. In particular, if no such $m$ exists, output $-1$.

### Sample Explanation For sample $1$, buying items costing $1\sim 5$ yuan requires $1\sim 5$ coins of $1$ yuan respectively, while buying an item costing $6$ yuan only requires $1$ coin of $6$ yuan. For sample $2$, buying an item costing $1$ yuan or $2$ yuan both requires $1$ coin, which does not satisfy the requirement that the number of coins needed is fewer. ### Constraints For $100\%$ of the testdata, $1\le n\le 10$, $1=a_1 < a_2 < a_3 < \cdots < a_n\le 10^9$, and $a_{i+1}$ is a multiple of $a_i$. **Hint: This problem uses bundled tests.** This problem has $4$ subtasks. | Subtask ID | $ n \le $ | Special Property | Score | |:-:|:-:|:-:|:-:| | $ 1 $ | $ 2 $ | None | 20 | | $ 2 $ | $ 10 $ | Guaranteed $a_i\le 10^3$ | 20 | | $ 3 $ | $ 10 $ | Guaranteed to have a solution | 30 | | $ 4 $ | $ 10 $ | None | 30 | ### Source | Item | Staff | |:-:|:-:| | idea | rui_er | | std | rui_er | | data | rui_er | | check | Kevin0501 | | solution | rui_er | Translated by ChatGPT 5