정규 동전 체계

동전 체계 $S$는 서로 다른 양의 정수로 이루어진, 비어 있지 않은 유한 집합이다. 각 원소는 실제 또는 가상의 화폐에서 쓰이는 동전의 액면가를 뜻한다. 예를 들어 캐나다에서 흔히 쓰는 동전 체계는 $\{1, 5, 10, 25, 100, 200\}$이고, 1은 1센트 동전을, 200은 200센트(2달러) 동전을 뜻한다. 어떤 동전 체계 $S$에서든 각 액면가의 동전은 무한히 있다고 가정한다. 또 $S$는 항상 1을 포함한다고 가정한다. 그러면 어떤 양의 정수든 $S$의 값을 중복을 허용해 더해서 만들 수 있다.

세계 어디서나 계산원은 다음 문제를 만나고, 또 푼다. 동전 체계와 손님에게 거슬러 줄 양의 정수 금액이 주어질 때, 그 금액을 정확히 맞추려면 동전이 최소 몇 개 필요한가? 캐나다의 계산원이 83센트를 거슬러 주는 경우를 보자. $25+25+10+10+10+1+1+1$처럼 동전 8개를 쓰는 방법이 있지만 최적은 아니다. $25+25+25+5+1+1+1$로 동전 7개만 쓰면 되고, 이 금액에서는 7개가 최소이다. 캐나다의 동전 체계는 그리디 알고리즘이 언제나 최적해를 내놓는 좋은 성질이 있고, 대부분 나라의 동전 체계도 그렇다. 그리디 알고리즘은 아직 남은 금액 이하인 액면가 중 가장 큰 동전을 고르는 일을 남은 금액이 0이 될 때까지 반복한다. 그리디 알고리즘이 항상 최적인 동전 체계를 정규(canonical) 체계라고 한다.

동전 체계 $S = \{c_1, c_2, \dots, c_n\}$이 주어질 때, $S$가 정규인지 아닌지 판정하라. $S$가 정규가 아니면 반례가 적어도 하나 있다. 즉 정확히 $x$를 만드는 데 필요한 동전의 최소 개수가 그리디 알고리즘이 쓰는 동전 개수보다 작은 양의 정수 $x$가 존재한다. 정규가 아닌 동전 체계의 예로 $\{1, 3, 4\}$가 있고, 6이 반례이다. 그리디 알고리즘은 $4+1+1$로 동전 3개를 쓰지만, 최적해는 $3+3$으로 2개이다. Dexter Kozen과 Shmuel Zaks가 보인 사실 하나가 도움이 된다. 동전 체계가 정규가 아니면, 가장 작은 반례는 가장 큰 액면가 두 개의 합보다 작다.

입력은 테스트 케이스 하나로 이루어진다. 첫째 줄에 동전 체계의 액면가 개수 $n$이 주어진다 ($2 \le n \le 100$). 둘째 줄에 $n$개의 액면가 $c_1\ c_2\ \dots\ c_n$이 공백으로 구분되어 주어진다. $c_1 = 1$이고 $c_1 < c_2 < \dots < c_n \le 10^6$이다.

동전 체계가 정규이면 canonical을, 정규가 아니면 non-canonical을 출력한다.