단어 2

0과 1로만 이루어진 이진 문자열에 작용하는 함수 $h$를 정의한다. $h$는 문자열의 모든 0을 1로, 모든 1을 두 글자 문자열 10으로 (동시에, 서로 독립적으로) 바꾼다. 예를 들어 $h$는 1001을 101110으로 보내고, 빈 문자열은 빈 문자열로 보낸다. $h$는 단사(injective) 함수이다. $h_k$는 $h$를 $k$번 합성한 함수를 뜻하며, $h_0$은 항등함수이므로 $h_0(w) = w$이다.

한 글자짜리 문자열 0에 대해 $h_k(0)$을 $k = 0, 1, 2, \dots$ 순서로 나열하면, 이 수열은 다음과 같이 시작한다.

0, 1, 10, 101, 10110, 10110101, ...

문자열 $x$가 문자열 $y$ 안에서 연속한 한 덩어리로 나타나면 $x$를 $y$의 부분 문자열이라고 한다. 정수 $k_1, k_2, \dots, k_n$이 주어질 때, 이어 붙인 문자열

$h_{k_1}(0)\,h_{k_2}(0)\cdots h_{k_n}(0)$

이 어떤 $m$에 대해 $h_m(0)$의 부분 문자열이 되는지 판정하고, 된다면 그러한 가장 작은 $m$을 구하여라.

첫 번째 줄에 정수 $n$ ($1 \le n \le 1{,}000{,}000$)이 주어진다. 두 번째 줄에는 $n$개의 음이 아닌 정수 $k_1, k_2, \dots, k_n$ ($0 \le k_i \le 10^9$)이 공백 하나로 구분되어 주어진다.

$h_{k_1}(0)\,h_{k_2}(0)\cdots h_{k_n}(0)$이 $h_m(0)$의 부분 문자열이 되는 가장 작은 음이 아닌 정수 $m$을 한 줄에 출력한다. 그러한 $m$이 존재하지 않으면 NIE를 출력한다.