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

_Lacatul dracului_ este o jucarie veche chinezeasca. Este format din inele de metal, montate pe cate o coada de lemn, astfel incat coada unui inel trece prin inelul urmator. Atunci cand lacatul este inchis, cozile sunt blocate intr-un suport de lemn de forma ovala.
 
!problema/lacat?moisil.jpg 70%!
 
Lacatul trebuie deschis, adica inelele trebuie desprinse din acest suport oval (trebuie date jos). Inelele sunt numerotate de la stanga la dreapta cu numere de la $1$ la $N$. Intr-un pas se poate elibera sau pune la loc un singur inel, respectand urmatoarele reguli:
 
# Primul inel poate fi eliberat sau pus la loc oricand.
# Fiecare inel, avand numarul de ordine $_i_ > 1$ poate fi eliberat sau pus la loc atunci si numai atunci cand inelul avand numarul de ordine $_i-1_$ se afla prins in suportul oval (este sus) si toate inele avand numarul de ordine mai mic decat $_i-1_$ sunt eliberate (sunt jos).
 
Lacatul este deschis daca toate inelele sunt eliberate (sunt jos).

!problema/lacat?moisil.jpg 60%!

h2. Date de intrare