以下任务是第 16 届波兰语 OI 第三阶段任务单词的明显难度版本。它没有在比赛本身中使用，而是为那些解决 “Words” 并想要更多的人提供的扩展。:-)设 为作用于由数字 0 和 1 组成的字符串的函数。 该函数 通过将每个数字 0 替换为 1 并将每个数字 1 替换为字符串 来转换字符串 。 例如 ， （即 为空字符串分配一个空字符串）。 请注意， 这是一个注入，或者说是一个一对一的函数。 我们 表示 由自身 times 组成的函数 。 特别是 是恒等函数 。 我们对以下形式的 字符串感兴趣 此序列以以下字符串开头：

, , , , , .

如果字符串作为连续（即一个块）子序列出现， 我们将该字符串 称为字符串 的子字符串。 给出了一个整数 序列。 你的任务是检查一个形式的 字符串是否是 for some 的子字符串，如果是，你会看到 minimal 这样的 。

输入格式 标准输入的第一行包含一个整数 。

标准输入的第二行包含 非负整数 （ ），由单空格分隔。

输出格式

您的程序应将 行打印到标准输出，每个测试单元一行。

您的程序应打印为标准输出 minimal non-negative integer ，例如 ，如果不存在 ，则为 NIE （波兰语中的 no） 的子字符串。

题意翻译 题目描述 下面的任务是第16届波兰语竞赛第三阶段的任务“单词”的一个明显的难度增强版本。它并没有在比赛中使用，但对于那些解决了“单词”的人来说，它是一个扩展 :) 。

函数 ℎ h 作用于由数字 0 0 和 1 1 组成的字符串，其通过将每一个数字 0 0 替换为 1 1，将每一个数字 1 1 替换为字符串 10 10 来独立且同时地变换字符串 ? w。

例如：

ℎ ( ‘ ‘ 1001 " )

‘ ‘ 101110 " h(‘‘1001")=‘‘101110"

ℎ ( ‘ ‘

" )

‘ ‘

" h(‘‘ ")=‘‘ "

其中例二即把空字符串赋值给空字符串。

注意， ℎ h 是一个一对一的函数。

我们用 ℎ ? h k 表示函数 ℎ h 使用 ? k 次。

特别的， ℎ 0 ( ? )

? h 0 (w)=w。

我们对 ?

0 , 1 , 2 , . . . k=0,1,2,... 的 ℎ ? ( ‘ ‘ 0 " ) h k (‘‘0") 形式的字符串感兴趣，这个序列为:

‘ ‘ 0 " , ‘ ‘ 1 " , ‘ ‘ 10 " , ‘ ‘ 101 " , ‘ ‘ 10110 " , ‘ ‘ 10110101 " , … ‘‘0",‘‘1",‘‘10",‘‘101",‘‘10110",‘‘10110101",…

如果字符串 ? x 在 ? y 中以一个连续的（即一个块）子串出现，我们就称 ? x 为字符串 ? y 的子串。给出整数 ? 1 , ? 2 , ? 3 , . . . , ? ? k 1 ​ ,k 2 ​ ,k 3 ​ ,...,k n ​ 的序列。你的任务是检查对于一些 ? m 来说， ℎ ? 1 ( ‘ ‘ 0 " ) ⋅ ℎ ? 2 ( ‘ ‘ 0 " ) ⋅ … ⋅ ℎ ? ? ( ‘ ‘ 0 " ) h k 1 ​

(‘‘0")⋅h k 2 ​

(‘‘0")⋅…⋅h k n ​

(‘‘0") 形式的字符串是否是 ℎ ? ( ‘ ‘ 0 " ) h m (‘‘0") 的子串，如果有，你应该找到最小的 ? m。

输入内容 输入的第一行包含一个整数 ? n， 1 ≤ ? ≤ 1000000 1≤n≤1000000。输入的第二行包含 ? n 个非负整数 ? 1 , ? 2 , ? 3 , . . . , ? ? k 1 ​ ,k 2 ​ ,k 3 ​ ,...,k n ​ ，用单个空格分隔。

输出内容 您的程序应该输出 ? t 行，每个测试输出一行。你的程序应该输出的最小非负整数 ? m，使 ℎ ? 1 ( ‘ ‘ 0 " ) ⋅ ℎ ? 2 ( ‘ ‘ 0 " ) ⋅ … ⋅ ℎ ? ? ( ‘ ‘ 0 " ) h k 1 ​

(‘‘0")⋅h k 2 ​

(‘‘0")⋅…⋅h k n ​

(‘‘0") 是 ℎ ? ( ‘ ‘ 0 " ) h m (‘‘0") 的子串。如果不存在 ? m，则输出 NIE（波兰语中的 no ）。

Translated By in_young_ren 翻译 yin_young_任

输入输出样例 输入 #1复制 2 1 2 输出 #1复制 4