Problem Description

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:

std::vector<bool> increasing_split(std::vector<int> 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

Input format:

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

Output Format

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.

5
3 1 4 5 5

001100

4
1 2 3 4

11111

Hint

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<N$

Subtasks