Frobenius Coin Problem: The Packaging Conundrum

Farmer Brown's cows are in a battle against McDonald's new product, the "McBeef Block", by sabotaging its packaging. The cows have decided to use a limited set of packaging box sizes to pack the McBeef Blocks. If McDonald's only offers boxes that can hold exactly (a_1, a_2, \dots, a_N) blocks (each available in unlimited quantity), then certain quantities of blocks cannot be purchased. Your task is to determine the largest number of McBeef Blocks that a customer cannot buy using these boxes. If every quantity can be purchased or there exists no finite upper bound to the quantities that cannot be purchased, output 0.

Formally, given (N) types of boxes ((1 \le N \le 10)) with capacities (a_1, a_2, \dots, a_N) (each (1 \le a_i \le 256)), if every positive integer can be represented as a linear combination (\sum_{i=1}^{N} x_i, a_i) (with nonnegative integers (x_i)) then output 0. Otherwise, output the largest positive integer that cannot be represented. It is guaranteed that if a largest nonrepresentable number exists, it does not exceed (2 \times 10^9).

Note: Any formula is given in (\LaTeX) format.

inputFormat

The first line contains a single integer (N). The second line contains (N) space-separated positive integers representing the sizes of the packaging boxes.

outputFormat

Output a single integer: the largest number of McBeef Blocks that cannot be purchased using the given box sizes, or 0 if every amount is attainable or the set of unattainable numbers is unbounded.

sample

3
3 6 10

17