RoAlgo PreOJI 2024 IX | sirpal

Task

LLM gives you a number $n$ and a sequence $a_1, a_2, \dots a_n$ of $n$ natural numbers. Now, he wants you to find for each position $i$ in the sequence if there exists a subsequence with the following properties:

• Its length is greater than or equal to $3$.
• $1 \leq x_1 < x_2 < \dots < x_k \leq n$, where $x_1, x_2, \dots, x_k$ are positions from the initial sequence used for the found subsequence.
• One of the chosen positions is $i$ and it is neither the first nor the last position in the subsequence (in other words, $x_1 \neq i$ and $x_k \neq i$).
• If we consider the values at the $k$ positions, the sequence is a palindrome (for example, the sequence $7 \ 14 \ 14 \ 7$ is a palindrome). A sequence $s_1 \ s_2 \dots s_q$ is a palindrome if and only if $s_1 = s_q, s_2 = s_{q-1}$ and so on.

LLM quickly found the answers for each position in the sequence, now it's your turn to achieve what LLM has achieved.

Input data

The first line of the input file sirpal.in contains $n$, the length of the sequence. The next line contains the $n$ values, representing the values in the sequence.

Output data

The first line of the output file sirpal.out will contain a binary sequence of length $n$, where the value at position $i$ is $1$ if we can find such a sequence that contains position $i$ and $0$ otherwise. The values will be displayed without spaces.

Constraints and clarifications

• $1 \leq n \leq 1\,000\,000$
• $1 \leq a_i \leq 1\,000\,000$ for each $i$ from $1$ to $n$

Example 1

sirpal.in

5
1 2 3 4 3

sirpal.out

00010

Explanation

We see that position $4$ is the only one that satisfies the conditions. We can choose the subsequence formed by indices $3, 4, 5$. We observe that it satisfies the conditions.

Example 2

sirpal.in

17
1 6 2 4 6 3 7 5 9 7 3 8 8 10 10 8 10

sirpal.out

00110011110011110

Explanation

For position $14$ (where the first $10$ is located) we can choose the subsequence $12, 14, 15, 16$. This is not the only option.