Canonical Coin Systems

A coin system $S$ is a finite nonempty set of distinct positive integers. Each element is a coin value, also called a denomination, in a real or imagined monetary system. The coin system in common use in Canada is $\{1, 5, 10, 25, 100, 200\}$, where 1 is a 1 cent coin and 200 is a 200 cent (2 dollar) coin. For any coin system $S$, assume there is an unlimited supply of coins of each denomination, and assume that $S$ contains 1, which guarantees that any positive integer can be written as a sum of values in $S$ with repetition allowed.

Cashiers all over the world face and solve the following problem. Given a coin system and a positive integer amount owed to a customer, what is the smallest number of coins required to dispense exactly that amount? Suppose a cashier in Canada owes a customer 83 cents. One solution is $25+25+10+10+10+1+1+1$, that is 8 coins, but it is not optimal, since the cashier could dispense $25+25+25+5+1+1+1$ instead, that is 7 coins, which is optimal here. The Canadian coin system has the property that the greedy algorithm always yields an optimal solution, as do the coin systems used in most countries. The greedy algorithm repeatedly chooses a coin of the largest denomination that is at most the amount still owed, until the amount owed reaches zero. A coin system for which the greedy algorithm is always optimal is called canonical.

Given a coin system $S = \{c_1, c_2, \dots, c_n\}$, determine whether $S$ is canonical or non-canonical. If $S$ is non-canonical then it has at least one counterexample, that is a positive integer $x$ such that the minimum number of coins required to dispense exactly $x$ is less than the number of coins used by the greedy algorithm. One non-canonical coin system is $\{1, 3, 4\}$, for which 6 is a counterexample: the greedy algorithm yields $4+1+1$ (3 coins), but an optimal solution is $3+3$ (2 coins). A useful fact, due to Dexter Kozen and Shmuel Zaks, is that if a coin system is non-canonical, then its smallest counterexample is less than the sum of the two largest denominations.

Input consists of a single case. The first line contains an integer $n$ ($2 \le n \le 100$), the number of denominations in the coin system. The next line contains the $n$ denominations as space separated integers $c_1\ c_2\ \dots\ c_n$, where $c_1 = 1$ and $c_1 < c_2 < \dots < c_n \le 10^6$.

Print canonical if the coin system is canonical, or non-canonical if the coin system is non-canonical.