시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB57116511825.821%

문제

$\textrm{mex}(S)$를 집합 $S$에 포함되지 않은 가장 작은 음이 아닌 정수로 정의한다. 길이가 $n$인 수열 $a_1, a_2, \cdots, a_n$이 주어질 때 $\textrm{mex}\left(\{a_i \times a_j \mid 1 \leq i \leq j \leq n \}\right)$을 구하여라. 즉, $a_i \times a_j$로 표현되지 않는 가장 작은 음이 아닌 정수 $x$를 구하여라.

입력

첫 번째 줄에 $n \, (1 \leq n \leq 2,000,000)$이 주어진다. 

두 번째 줄에는 수열 $a_1, a_2, \cdots, a_n \, (0 \leq a_i \leq 2,000,000)$이 주어진다.

출력

$\textrm{mex}\left(\{a_i \times a_j \mid 1 \leq i \leq j \leq n \}\right)$을 첫 번째 줄에 출력하여라.

예제 입력 1

3
0 1 2

예제 출력 1

3

힌트

만들어지는 집합은 ({0,1,2,4})가 되고, 이 집합에 포함되지 않는 가장 작은 음이 아닌 정수는 3이다.

출처

University > POSTECH > 2021 POSTECH Programming Contest H번