题目描述

Boris 和 Ihor 找到了一个由 $N$ 个正整数组成的序列 $a_0,a_1,\ldots,a_{N-1}$，并想在两人之间分配这些数。由于无法就分配方案达成一致，他们请你担任仲裁者。

在作出任何决定之前，你可以看到整个序列。随后，你从左到右依次处理 $a$ 的元素：先处理 $a_0$，再处理 $a_1$，直至 $a_{N-1}$。处理每个元素时，你必须将它恰好交给 Boris 和 Ihor 中的一人。

两人都要求自己收到的元素按接收顺序构成严格递增序列。也就是说，交给某人的每个元素都必须严格大于此前交给他的最后一个元素。某人收到的第一个元素可以是任意值，也允许其中一人不收到任何元素。

对于从 $0$ 到 $N$ 的每个整数 $K$，请判断能否完成分配，使 Boris 恰好收到 $K$ 个元素，并且两人得到的序列都严格递增。每个 $K$ 都应视为一次相互独立的问题。

例如，令 $a=[3,1,4,5,5]$。

• 当 $K=3$ 时，将 $a_0=3$、$a_2=4$ 和 $a_3=5$ 交给 Boris，将 $a_1=1$ 和 $a_4=5$ 交给 Ihor。Boris 得到 $3,4,5$，Ihor 得到 $1,5$，两个序列都严格递增，因此 $K=3$ 可行。
• 当 $K=0$ 时，Boris 什么也得不到，Ihor 得到所有元素。Ihor 的序列以 $3,1$ 开头，并非严格递增，因此 $K=0$ 不可行。

在本例中，只有 $K=2$ 和 $K=3$ 可行。

实现细节

你需要实现以下函数：

std::vector<bool> increasing_split(std::vector<int> a)

• $a$：由 $N$ 个数组成的序列。

函数必须返回一个长度恰好为 $N+1$ 的布尔数组。若可以进行分配，使 Boris 恰好收到 $i$ 个元素且两个结果序列都严格递增，则下标 $i$ 处的元素应为 true，否则为 false。每个测试中该函数恰好调用一次。

输入格式

输入格式：

• 第 $1$ 行：一个整数 $N$；
• 第 $2$ 行：$N$ 个整数 $a_0,a_1,\ldots,a_{N-1}$。

输出格式

若返回数组的长度不是 $N+1$，样例评测器会输出 WA: Returned array does not have size N+1。否则，它会输出一个长度为 $N+1$ 的二进制串；若 $K=i$ 可行，则下标 $i$ 处的字符为 1，否则为 0。

5
3 1 4 5 5

001100

4
1 2 3 4

11111

提示

样例 1 解释

这里 $a=[3,1,4,5,5]$。对于每个 $K$：

• $K=0$：不存在合法分配，答案为 0；
• $K=1$：不存在让 Boris 恰好收到一个元素的合法分配，答案为 0；
• $K=2$：将 $a_1=1$ 和 $a_4=5$ 交给 Boris，将 $a_0=3$、$a_2=4$ 和 $a_3=5$ 交给 Ihor。两个序列都严格递增，答案为 1；
• $K=3$：存在上文所述的合法分配，答案为 1；
• $K=4$ 和 $K=5$：不存在合法分配，答案均为 0。

样例 2 解释

这里 $a=[1,2,3,4]$ 本身已经严格递增。无论如何分配，两人得到的序列都会严格递增。因此从 $0$ 到 $4$ 的每个 $K$ 都可行。

限制

• $2\le N\le 4\cdot 10^5$
• 对每个 $0\le i<N$，均有 $1\le a_i\le 10^9$

子任务