P17270 [eJOI 2026] Increasing Split

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$ 可行。 ### 实现细节 你需要实现以下函数： ```cpp std::vector increasing_split(std::vector 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`。

### 样例 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