Red Ball Weight Transformation

We are given n balls in a row, numbered from \(1\) to \(n\). Initially every ball is red and the \(i\)th ball has weight \(p_i\). It is guaranteed that \(n\) is odd and \(p=[p_1, p_2,\dots,p_n]\) is a permutation of \(\{1,2,\dots,n\}\). You must perform exactly \(\frac{n-1}{2}\) operations. In each operation you must do the following:

1. Choose a red ball at position \(i\) (with \(1\le i\le n\)) such that there is at least one red ball to its left (i.e. in positions \(1,2,\dots,i-1\)) and at least one red ball to its right (i.e. in positions \(i+1,\dots,n\)).
2. Let \(j\) be the largest index less than \(i\) with a red ball, and \(k\) the smallest index greater than \(i\) with a red ball. Then, color ball \(i\) and ball \(k\) blue (i.e. they will no longer be available) and update the weight of ball \(j\) as follows:
   You must perform exactly one of the following two updates:
   \(p_j \leftarrow \max(p_i,\,p_j,\,p_k)\) or \(p_j \leftarrow \min(p_i,\,p_j,\,p_k)\).

It is easy to see that after \(\frac{n-1}{2}\) operations exactly one red ball remains. For every \(x \in \{1,2,\dots,n\}\) you must decide if it is possible to perform the operations (choosing the order and the update in each operation arbitrarily subject to the rules) so that the final remaining red ball has weight \(x\).

Note. Since the left‐most ball in the current red sequence is never chosen (because it has no red ball to its left), it turns out that the final red ball is always the one originally in the first position. However, its weight gets updated along the way via merges with other balls. In essence, the process is equivalent to reducing the original red sequence (of odd length) by repeatedly removing two consecutive balls (from the interior) and updating the left neighbour’s weight to either the minimum or maximum of the triple. The answer for each \(x\) is determined by the possible values that can be propagated to the surviving ball at position \(1\).

All formulas are given in \(\LaTeX\) format.

inputFormat

The first line contains an odd integer \(n\) \((1\le n\le 15)\) representing the number of balls. The second line contains \(n\) space‐separated integers \(p_1,p_2,\dots,p_n\), which is a permutation of \(\{1,2,\dots,n\}\).

outputFormat

Output a binary string of length \(n\) (with no spaces). The \(x\)th character (for \(1\le x\le n\)) should be 1 if it is possible to obtain a final red ball with weight \(x\) and 0 otherwise.

For example, if \(n=3\) and the only possible final weights are \(1\) and \(3\), then the output should be 101.

sample

1
1

1