Words 2

Define a function $h$ that acts on binary strings (strings over the digits 0 and 1). $h$ transforms a string by replacing every 0 with 1 and every 1 with the two-character string 10, with all replacements done simultaneously and independently. For example, $h$ maps 1001 to 101110, and it maps the empty string to the empty string. The function $h$ is injective. Let $h_k$ denote $h$ composed with itself $k$ times; $h_0$ is the identity, so $h_0(w) = w$.

Consider the one-character string 0 and the strings $h_k(0)$ for $k = 0, 1, 2, \dots$. This sequence begins:

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

A string $x$ is a substring of a string $y$ if it occurs in $y$ as a contiguous block. Given integers $k_1, k_2, \dots, k_n$, decide whether the concatenation

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

is a substring of $h_m(0)$ for some $m$, and if so find the smallest such $m$.

The first line contains one integer $n$ ($1 \le n \le 1{,}000{,}000$). The second line contains $n$ non-negative integers $k_1, k_2, \dots, k_n$ ($0 \le k_i \le 10^9$), separated by single spaces.

Print the smallest non-negative integer $m$ such that $h_{k_1}(0)\,h_{k_2}(0)\cdots h_{k_n}(0)$ is a substring of $h_m(0)$. If no such $m$ exists, print NIE.