Simplifying Currency Systems

In the country of netizens, there are \(n\) different denominations of currency. The \(i\)-th currency has a value \(a[i]\) and is available in infinite quantity. We denote a currency system with \(n\) types and denominations \(a[1\dots n]\) as \((n,a)\).

In a proper (or complete) currency system, every nonnegative integer \(x\) can be represented; that is, for every \(x\ge0\) there exist nonnegative integers \(t[i]\) such that \[ \sum_{i=1}^{n} t[i]\times a[i] = x. \] However, in netizens' country the system may be imperfect and some amounts may not be representable. For example, in the system \((3,[2,5,9])\), the amounts \(1\) and \(3\) cannot be represented.

Two systems \((n,a)\) and \((m,b)\) are considered equivalent if for every nonnegative integer \(x\), either both systems can represent \(x\) or neither can.

Netizens wish to simplify their currency system. They want to find another system \((m,b)\) which is equivalent to the original \((n,a)\) but with the number of denominations \(m\) as small as possible. Your task is to compute the smallest possible \(m\).

inputFormat

The first line contains an integer \(n\) representing the number of coin types. The second line contains \(n\) space-separated positive integers \(a[1],a[2],\dots,a[n]\), which are the coin denominations.

outputFormat

Output a single integer representing the smallest \(m\) such that there exists a currency system \((m,b)\) equivalent to the original currency system.

sample

3
2 5 9

2