Cerință

LLM vă dă un număr $n$ și un șir $a_1, a_2, \dots a_n$ de $n$ numere naturale. Acum, el vrea să aflați pentru fiecare poziție $i$ din șir dacă există un subșir cu următoarele proprietăți:

• Lungimea lui este mai mare sau egală cu $3$.
• $1 \leq x_1 < x_2 < \dots < x_k \leq n$, unde $x_1, x_2, \dots, x_k$ sunt pozițiile din șirul inițial folosit pentru subșirul găsit.
• Una din pozițiile alese este $i$ și nu este prima sau ultima poziție din subșir (cu alte cuvinte, $x_1 \neq i$ și $x_k \neq i$).
• Dacă considerăm valorile din cele $k$ poziții, șirul este palindrom (de exemplu, șirul $7 \ 14 \ 14 \ 7$ este palindrom). Un șir $s_1 \ s_2 \dots s_q$ este palindrom dacă și numai dacă $s_1 = s_q, s_2 = s_{q-1}$ și așa mai departe.

LLM a aflat repede răspunsurile pentru fiecare poziție din șir, acum e rândul vostru să reușiți ceea ce a reușit LLM.

Date de intrare

Pe prima linie a fișierului de intrare sirpal.in se găsește $n$, lungimea șirului. Pe următoarea linie se află cele $n$ valori, reprezentând valorile din șir.

Date de ieșire

Pe prima linie a fișierului de ieșire sirpal.out se va găsi un șir binar de lungime $n$, unde valoarea de pe poziția $i$ este $1$ dacă putem găsi un asemenea șir care să conțină poziția $i$ și $0$ în caz contrar. Valorile se vor afișa fără spații.

Restricții și precizări

• $1 \leq n \leq 1 \ 000 \ 000$
• $1 \leq a_i \leq 1 \ 000 \ 000$ pentru fiecare $i$ de la $1$ la $n$

Exemplul 1

sirpal.in

5
1 2 3 4 3

sirpal.out

00010

Explicație

Observăm că poziția $4$ este singura care verifică condițiile. Putem să alegem subșirul format din indicii $3, 4, 5$. Observăm că acesta respectă condițiile.

Exemplul 2

sirpal.in

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

sirpal.out

00110011110011110

Explicație

Pentru poziția $14$ (unde se află primul $10$) putem alege subșirul $12, 14, 15, 16$. Observăm că aceasta nu este singura variantă.