P17270 [eJOI 2026] Increasing Split

Boris and Ihor have found a sequence $a$ of $N$ positive integers, $a_0,a_1,\ldots,a_{N-1}$, and want to split it between themselves. Unable to agree on the split, they have asked you to act as their arbiter. Before making any decisions, you are shown the entire sequence. You then process the elements of $a$ from left to right: first $a_0$, then $a_1$, and so on up to $a_{N-1}$. As each element is processed, you must give it to exactly one of Boris and Ihor. Both insist that the elements they receive form a strictly increasing sequence in the order received. Every element you give to a person must be strictly greater than the previous element given to that same person. The first element a person receives may have any value, and one person may receive no elements at all. For every integer $K$ from $0$ to $N$, determine whether it is possible to split the elements so that Boris receives exactly $K$ elements and both resulting sequences are strictly increasing. Treat every value of $K$ as an independent question. For example, let $a=[3,1,4,5,5]$. - For $K=3$, give $a_0=3$, $a_2=4$, and $a_3=5$ to Boris, and give $a_1=1$ and $a_4=5$ to Ihor. Boris receives $3,4,5$ and Ihor receives $1,5$; both sequences are strictly increasing, so $K=3$ is possible. - For $K=0$, Boris receives nothing and Ihor receives everything. Ihor's sequence begins with $3,1$, so it is not strictly increasing and $K=0$ is impossible. For this example, the only possible values of $K$ are $2$ and $3$. ### Implementation details Implement the following function: ```cpp std::vector increasing_split(std::vector a) ``` - $a$: the sequence of $N$ numbers. The function must return a boolean array of size exactly $N+1$. Its element at index $i$ must be `true` if the elements can be split so that Boris receives exactly $i$ elements and both resulting sequences are strictly increasing, and `false` otherwise. The function is called exactly once per test.

Input format: - line $1$: one integer $N$; - line $2$: $N$ integers $a_0,a_1,\ldots,a_{N-1}$.

If the returned array does not have size $N+1$, the sample grader prints `WA: Returned array does not have size N+1`. Otherwise, it prints a binary string of length $N+1$ whose character at index $i$ is `1` if $K=i$ is possible, and `0` otherwise.

### Explanation of example 1 Here $a=[3,1,4,5,5]$. For each $K$: - $K=0$: no valid split exists, so the answer is `0`; - $K=1$: no valid split exists in which Boris receives exactly one element, so the answer is `0`; - $K=2$: give $a_1=1$ and $a_4=5$ to Boris, and $a_0=3$, $a_2=4$, and $a_3=5$ to Ihor. Both sequences are strictly increasing, so the answer is `1`; - $K=3$: a valid split exists as described above, so the answer is `1`; - $K=4$ and $K=5$: no valid split exists, so both answers are `0`. ### Explanation of example 2 Here $a=[1,2,3,4]$ is already strictly increasing. Regardless of how the elements are split, both people receive strictly increasing sequences. Hence every $K$ from $0$ to $4$ is possible. ### Constraints - $2\le N\le 4\cdot 10^5$ - $1\le a_i\le 10^9$ for every $0\le i