Stiva

Olivius d’Info a primit de ziua lui o stivă şi s-a bucurat foarte tare. S-a tot gândit ce să facă cu ea şi a inventat un joc de logică pentru colegii lui de clasă.

În prima fază el a scris mai multe bileţele, conţinând fiecare câte o permutare a primelor $n$ numere naturale nenule: $1, 2, 3, ..., n$. Bileţelele scrise conţin permutări pentru diferite valori ale lui $n$.

A clasificat aceste permutări în permutări stivuite şi permutări nestivuite.

O permutare este stivuită dacă se poate obţine pe parcursul introducerii în stivă a numerelor $1, 2, 3, ...,n$ în această ordine, prin extragerea elementelor, în ordinea indicată în permutare.

O permutare nestivuită este o permutare care NU se poate obţine prin procedeul de mai sus.

Respectând procedeul lui Olivius, pentru $n=4$, permutarea stivuită $(2,1,3,4)$ se obţine astfel:

Figura 1 din enunțul original al problemei Stiva.Mărește schema ↗

Succesiunile $(3,1,2,4)$ şi $(4,2,1,3)$ sunt permutări nestivuite.

În faza a doua, unele bileţele au fost scurtate din stânga şi/sau din dreapta. Astfel, din permutarea stivuită $(2,1,3,4)$ se pot obţine succesiuni de lungime mai mică: $(1,3,4), (2,1,3), (1,3),(3)$ etc.

Orice succesiune care aparţine unei permutări stivuite, poate aparţine şi unei permutări nestivuite. De exemplu, succesiunea $(2,1,3)$ aparţine atât permutării stivuite $(2,1,3,4)$, cât şi permutării nestivuite $(4,2,1,3)$.

Cerinţă

Dându-se mai multe succesiuni de numere naturale distincte, determinaţi, pentru fiecare dintre acestea, dacă aparţin cel puţin unei permutări stivuite.

Date de intrare

Fişierul stiva.in conţine un set de cinci succesiuni de elemente, după cum urmează:

• pe prima linie un număr natural $k$, reprezentând numărul de elemente al fiecăreia dintre cele cinci succesiuni;
• pe fiecare din următoarele cinci linii câte $k$ numere naturale nenule, separate prin câte un spaţiu, reprezentând elementele unei succesiuni.

Date de ieșire

Fişierul stiva.out va conţine $5$ linii, pe fiecare linie câte un număr natural astfel:

• 1 – dacă succesiunea curentă aparţine unei permutări stivuite;
• 0 – dacă succesiunea curentă nu aparţine unei permutări stivuite.

Răspunsurile se scriu pe câte o linie, în ordinea apariţiilor succesiunilor în fişierul de intrare.

Restricții și precizări

• $1 \leq$ valoarea elementelor din succesiune $\leq 2 \ 000 \ 000 \ 000$
• diferenţa dintre cel mai mare şi cel mai mic element al succesiunii nu depăşeşte $50 \ 000$
• pentru $50\%$ din teste, elementele din succesiune nu depăşesc $50 \ 000$
• elementele dintr-o succesiune sunt distincte două câte două.

Exemplu

stiva.in

3
1 3 4
2 1 3
3 1 2
1 2 4
1 4 2

stiva.out

1
1
0
1
0

Explicație

$n=3$, avem cinci succesiuni de numere, fiecare de lungime $3$.

• succesiunea $(1,3,4)$ aparţine unei permutări stivuite (răspuns corect $1$);
• succesiunea $(2,1,3)$ aparţine unei permutări stivuite (răspuns corect $1$);
• succesiunea $(3,1,2)$ nu aparţine niciunei permutări stivuite (răspuns corect $0$);
• succesiunea $(1,2,4)$ aparţine unei permutări stivuite (răspuns corect $1$);
• succesiunea $(1,4,2)$ nu aparţine niciunei permutări stivuite (răspuns corect $0$).