AT_utpc2024_k.K-rep Array

对于正整数 $K$，我们称仅包含正整数的数列 $V$ 是 $K$-rep 的，当且仅当下述条件成立：

• 存在一个仅包含正整数且长度为 $K$ 的数列 $B$，使得将 $B$ 重复 $10^{100}$ 次形成的新数列 $B'$，$V$ 作为 $B'$ 的一个连续子序列出现。

现在给定一个长度为 $N$ 的数列 $A = (A_1, A_2, \ldots, A_N)$，其中每个 $A_i$ 是正整数或 $-1$。对于 $K=1,2,\ldots,N$，请解答以下问题：

是否存在一个仅包含正整数且长度为 $N$ 的数列 $V = (V_1, V_2, \dots, V_N)$，满足当 $A_i \neq -1$ 时 $V_i = A_i$，并且 $V$ 是 $K$-rep？

输入从标准输入读入，格式如下：

$N$
$A_1\ A_2\ \dots\ A_N$

输出一个长度为 $N$ 的字符串。第 $i$ 个字符表示对于 $K = i$ 时，是否存在满足要求的数列。存在时输出 1，不存在时输出 0。

样例解释 1

例如，对于一个仅包含正整数且长度为 $N$ 的数列 $V = (V_1, V_2, \dots, V_N)$，如果满足所有 $A_i \neq -1$ 时 $V_i = A_i$，一种可能为 $V = (1, 2, 3, 2, 1)$。当 $K = 4$ 时，取 $B = (2, 3, 2, 1)$，那么 $B'$ 中包含了 $(1, 2, 3, 2, 1)$ 作为连续子序列，因此 $(1, 2, 3, 2, 1)$ 是 $K$-rep。

数据范围

• 所有输入均为整数。
• $1 \leq N \leq 2\times 10^5$
• $1 \leq A_i \leq N$ 或 $A_i = -1$。

由 ChatGPT 5 翻译