거스름돈 없이

면접 대비

시간 제한1초메모리 제한1024 MB

요약

동전 N개의 값이 주어질 때, 동전을 일부 골라 더해서 만들 수 없는 가장 작은 양의 정수를 구합니다.

문제

잭은 값이 각각 $M_1$ , $M_2$ , \dots, $M_N$ 인 동전 $N$ 개를 가지고 있다. 이 동전들로 거스름돈 없이 정확히 지불할 수 없는 가장 작은 양의 금액을 구하라.

첫 번째 줄에 동전의 개수 $N$ ( $1 \le N \le 1\,000$ )이 주어진다. 두 번째 줄에는 동전의 값 $M_i$ ( $1 \le M_i \le 1\,000\,000$ )가 정수 $N$ 개로 주어진다.

잭이 지불할 수 없는 가장 작은 양의 정수를 한 줄에 출력한다.