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:

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 de intrare stiva1.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 de ieșire stiva1.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<= valoarea elementelor din succesiune <= 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:

stiva1.in

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

stiva1.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).