本题是第 16 届波兰信息学奥林匹克竞赛（POI）第三阶段题目 Words 的加强版。它并未在正式比赛中使用，而是为那些解决了“Words”并希望进一步挑战的选手准备的扩展题。 :-)

设 $h$ 是定义在由数字 0 和 1 组成的字符串上的函数。函数 $h$ 通过将字符串 $w$ 中的每个数字 0 替换为 1，并将每个数字 1 替换为字符串 "10" 来转换该字符串（替换是独立且同时进行的）。例如，$h(\text{"1001"}) = \text{"101110"}$，$h(\text{""}) = \text{""}$（即对空字符串应用 $h$ 得到空字符串）。注意 $h$ 是单射。我们用 $h^k$ 表示 $h$ 与自身的 $k$ 次复合。特别地，$h^0$ 是恒等函数，$h^0(w) = w$。

我们关注形式为 $h^k(\text{"0"})$ 的字符串，其中 $k = 0, 1, 2, 3, \ldots$。前几个这样的字符串为：

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

如果字符串 $x$ 作为连续子序列出现在字符串 $y$ 中，则称 $x$ 是 $y$ 的子串。给定一个自然数序列 $k_1, k_2, \ldots, k_n$，目标是检查字符串

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

是否为某个 $h^m(\text{"0"})$ 的子串，如果是，求出最小的 $m$。其中符号 "$\cdot$" 表示字符串的拼接。

输入格式

标准输入的第一行包含一个整数 $n$，$1 \leq n \leq 1\,000\,000$。第二行包含 $n$ 个非负整数 $k_1, k_2, \ldots, k_n$（$0 \leq k_i \leq 10^9$），以空格分隔。

输出格式

程序应输出一行，包含使得

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

成为 $h^m(\text{"0"})$ 的子串的最小非负整数 $m$，如果不存在这样的 $m$，则输出单词 "NIE"（波兰语中的“不”）。

样例

样例输入 1

2
1 2

样例输出 1

4

第一个测试用例中的字符串是 $“\texttt{110}”$ —— 它是 $h^4(“\texttt{0}”)=“\texttt{10110}”$ 的子串。第二个测试单元中的字符串是 $“\texttt{100}”$，它不是任何 $h^m(“\texttt{0}”)$ 的子串。

样例输入 2

2
2 0

样例输出 2

NIE