The following task is a significantly harder version of task Words from the third stage of 16th Polish OI. It wasn't used in the contest itself, but is an extension for those who solved "Words" and want more. :-)

Let $h$ be a function defined on strings consisting of digits 0 and 1. The function $h$ transforms a string $w$ by replacing (independently and simultaneously) each digit 0 by 1 and each digit 1 by the string "10". For example, $h(\text{"1001"}) = \text{"101110"}$, $h(\text{""}) = \text{""}$ (i.e., applying $h$ to the empty string yields the empty string). Note that $h$ is injective. By $h^k$ we denote the $k$-fold composition of $h$ with itself. In particular, $h^0$ is the identity function $h^0(w) = w$.

We are interested in strings of the form $h^k(\text{"0"})$ for $k = 0, 1, 2, 3, \ldots$. The first few such strings are:

$$ \text{"0"}, \text{"1"}, \text{"10"}, \text{"101"}, \text{"10110"}, \text{"10110101"}. $$

We say that a string $x$ is a substring of a string $y$ if it occurs as a contiguous subsequence of $y$. We are given a sequence of natural numbers $k_1, k_2, \ldots, k_n$. The goal of the problem is to check whether the string

$$ h^{k_1}(\text{"0"}) \cdot h^{k_2}(\text{"0"}) \cdot \ldots \cdot h^{k_n}(\text{"0"}) $$

is a substring of $h^m(\text{"0"})$ for some $m$, and if so, to find the smallest such $m$. Here the operation "$\cdot$" denotes concatenation of strings.

Input

The first line of the standard input contains a single integer $n$, $1 \leq n \leq 1\,000\,000$. The second line contains $n$ non‑negative integers $k_1, k_2, \ldots, k_n$ ($0 \leq k_i \leq 10^9$) separated by single spaces.

Output

Your program should output a single line containing the smallest non‑negative integer $m$ such that

$$ h^{k_1}(\text{"0"}) \cdot h^{k_2}(\text{"0"}) \cdot \ldots \cdot h^{k_n}(\text{"0"}) $$

is a substring of $h^m(\text{"0"})$, or the single word "NIE" (Polish for "NO") if no such $m$ exists.

Example 1

Input

2
1 2

Output

4

The string from the first test case is $“\texttt{110}”$ - it is a substring of $h_4(“\texttt{0}”)=“\texttt{10110}”$. In the second test unit there is a string $“\texttt{100}”$, which is not a substring of $h_m(“\texttt{0}”)$ for any $m$.

Example 2

Input

2
2 0

Output

NIE