O pereche de numere naturale (x,y) se numeste p-ordonata daca x si y au paritate diferita, cu x>y, sau daca x si y au aceeasi paritate.
Exemplu: (7,4), (8,7), (7,9) sunt perechi p-ordonate, dar (7,8), (8,9) nu sunt perechi p-ordonate.
Un sir, format din 2*n numere naturale, se numeste p-ordonat daca perechile de forma (x,y) sunt p-ordonate, pentru orice x, dintre primii n termeni ai sirului, si orice y, dintre ultimii n termeni ai sirului.
Fisierul bac.txt contine numere naturale din intervalul [0,10^6]: pe prima linie un numar nenul, n, iar pe a doua linie un sir de 2*n numere. Se cere sa se afiseze pe ecran mesajul DA, in cazul in care sirul aflat in fisier este p-ordonat, sau mesajul NU, in caz contrar. Proiectati un algoritm eficient din punctul de vedere al timpului de executare si al memoriei utilizate.
Exemplu: pentru sirul 22 37 21 8 15 2 3 14 4 5 (n=5) se afiseaza pe ecran mesajul DA.
- Date de intrare
- Fisierul bac.txt: pe prima linie n, pe a doua linie sirul de 2n numere.
- Date de iesire
- Se afiseaza 'DA' daca sirul este p-ordonat, altfel 'NU'.
- Restrictii
- 1 <= n, valori in [0,10^6]
Exemple
Exemplul 1
Intrare
5 22 37 21 8 15 2 3 14 4 5
Iesire
DA
Exemplul 2
Intrare
5 22 36 20 8 14 44 42 4 2 5
Iesire
DA