meneaito

Meneaito

== include(page="template/taskheader" task_id="meneaito") ==

Pentru că a stat prea mult la festivitatea de premiere a concursului No Stress, Mihăiţă a întarziat şi a pierdut începutul balului. Darnic din fire, el vrea să-i facă cinste prietenei sale cu banii căştigţi la concurs. Ajuns in club, Mihăiţa observă câteva lucruri ciudate.
Putem să ne imaginam Barletto ca fiind o matrice patratică de dimensiune $NxN$, având intrarea pe poziţia $(1, 1)$. Pe fiecare coloană $i$, $2$ ≤ $i$ ≤ $N-1$ se află câte un petrecăreţ care dansează meneaito. Mihăiţa cunoaşte pentru fiecare petrecăreţ de pe linia $i$, poziţia iniţială în care se află $(A[i], i)$, şi că acesta danseaza doar pe coloana sa, intre poziţiile $(A[i], i)$ şi $(B[i], i)$ în modul urmator : în fiecare secundă se mişcă câte o casuţă, în acelaşi sens până întălneşte unul din capătul spaţiului în care poate să danseze, moment în care îşi schimbă sensul. Deoarece in club e prea mult fum si Mihăiţă nu stie ca prietena lui se distrează la masa artiştilor, care se afla pe pozitia (N, N), el nu intră in club decat dupa ce reuseste sa o vada pe prietena lui. Mihăiţă poate sa işi vadă prietenaîntr-un moment de timp t, dacă nici un petrecăreţ nu se află în acel moment pe una din poziţiile $(i, i)$, $2$ ≤ $i$ ≤ $N-1$. Deoarece Mihăiţă nu este foarte răbdător, el se hotăraşte că dacă nu reuşeşte sa-si vada prietena in $200 000$ de secunde o să plece acasă.

Pentru că a stat prea mult la festivitatea de premiere a concursului No Stress, Mihăiţă a întarziat şi a pierdut începutul balului. Darnic din fire, el vrea să-i facă cinste prietenei sale cu banii căştigaţi la concurs. Ajuns in club, Mihăiţa observă câteva lucruri ciudate.
Putem să ne imaginam Barletto ca fiind o matrice patratică de dimensiune $NxN$, având intrarea pe poziţia $(1, 1)$. Pe fiecare coloană $i$, $2$ ≤ $i$ ≤ $N-1$ se află câte un petrecăreţ care dansează meneaito. Mihăiţa cunoaşte pentru fiecare petrecăreţ de pe coloana $i$, poziţia iniţială în care se află $(A[i], i)$, şi că acesta danseaza doar pe coloana sa, intre poziţiile $(A[i], i)$ şi $(B[i], i)$ în modul urmator : în fiecare secundă se mişcă câte o casuţă, în acelaşi sens până întălneşte unul din capătul spaţiului în care poate să danseze, moment în care îşi schimbă sensul. Deoarece în club e prea mult fum si Mihăiţă nu ştie ca prietena lui se distrează la masa artiştilor, care se află pe poziţia $(N, N)$, el nu intră in club decat după ce reuşeşte să o vadă pe aceasta. Mihăiţă o poate vedea într-un moment de timp t, dacă nici un petrecăreţ nu se află în acel moment pe una din poziţiile $(i, i)$, $2$ ≤ $i$ ≤ $N-1$. Deoarece Mihăiţă nu este foarte răbdător, el o să plece acasa dacă nu reuşeste sa-şi vadă prietena in $200 000$ de secunde.

Să se afişeze momentul de timp în care Mihăiţă poate arunca berea, sau $-1$ in cazul în care Mihăiţă se plictiseşte şi pleacă acasă.

Să se afişeze momentul de timp minim în care Mihăiţă îsi gaseste prietena, sau $-1$ in cazul în care Mihăiţă se plictiseşte şi pleacă acasă.

h2. Date de intrare

Fişierul de intrare $meneaito.in$ conţine pe prima linie un număr natural $N$, dimensiunea clubului Barletto. Pe următoarele două linii se află N-2 numere, reprezentând poziţiile descrise de A, respectiv B.

Fişierul de intrare $meneaito.in$ conţine pe prima linie un număr natural $N$, dimensiunea clubului Barletto. Pe următoarele două linii se află $N-2$ numere, reprezentând poziţiile descrise de A, respectiv B.

h2. Date de ieşire

În fişierul de ieşire $meneaito.out$ va conţine un singur număr întreg, timpul minim cerut sau -1.

În fişierul de ieşire $meneaito.out$ va conţine un singur număr întreg, timpul minim cerut sau $-1$.

h2. Restricţii

table(example). |_. meneaito.in |_. meneaito.out |
| 5
2 2 2

3 4 5

3 5 5

| 3
|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="meneaito") ==