Fişierul intrare/ieşire:	arbori2.in, arbori2.out	Sursă	utcn-2021
Autor	Tudor Muresan	Adăugată de	Ciprian Oprisa •cypry
Timp execuţie pe test	0.1 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Arbori binari de căutare ordonați

Se consideră toţi arborii binari de căutare distincţi având $n$ noduri, cu cheile nodurilor de la $1$ la $n$ şi care au secvenţa de traversare INordine: $1 \: 2 \: 3 \: \ldots \: n$ . Se ordonează arborii de mai sus în ordinea lexicografică descrescătoare a secvenţelor de traversare PREordine. De exemplu pentru $n=4$ avem arborii de mai jos:

Se observă că toţi cei 14 arbori distincţi au secvenţa de traversare INordine $1 \: 2 \: 3 \: 4$ iar secvenţele de traversare PREordine sunt în ordine lexicografică descrescatoare.

Fiind dată secvenţa de traversare PREordine a unui arbore de căutare definit mai sus se cere să se calculeze numărul de ordine al arborelui.

Date de intrare

Fişierul de intrare arbori2.in conţine mai multe exemple de test. Un exemplu are pe prima linie un întreg $n$ precizând numărul nodurilor arborelui binar de căutare (având cheile $1, 2, 3, \ldots, n$ şi secventa de traversare INordine $1 \: 2 \: 3 \: \ldots \: n$ ). Pe linia următoare sunt $n$ întregi separaţi de un spaţiu reprezentând secvenţa cheilor obţinuta la traversarea PREordine a arborelui binar de căutare. Fişierul se termină cu o linie conţinând un 0.

Date de ieşire

Fişierul de ieşire arbori2.out conţine câte o linie pentru fiecare exemplu de test, pe care se tipăreşte numărul exemplului de test urmat de ':' şi de numărul de ordine, luat modulo 9999991, al arborelui binar de căutare cu secvenţa cheilor la traversarea PREordine dată.

Restricţii

$1 \leq n \leq 200$

Exemplu

arbori2.in	arbori2.out
4 3 1 2 4 30 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 0	1:7 2:5583241

Precizări

Un arbore binar de căutare este un arbore binar ce satisface următoarele condiţii:

subarborele stâng al unui nod conţine numai noduri cu chei mai mici decât cheia nodului
subarborele drept al unui nod conţine numai noduri cu chei mai mari decât cheia nodului
atât subarborele stâng al unui nod, cât şi cel drept sunt arbori binari de căutare

O traversare PREordine (Rădacină-Stânga-Dreapta) a arborelui tipăreşte cheia rădăcinii urmată de traversarea subarborelui stâng şi apoi a celui drept. O traversare INordine (Stânga-Rădacină-Dreapta) a arborelui tipăreşte subarborele stâng, apoi tipăreşte cheia rădăcinii şi la sfârşit subarborele drept. De exemplu traversarea arborelui de mai sus este:

PREordine: $6 \: 4 \: 2 \: 1 \: 3 \: 5 \: 9 \: 7 \: 8$
INordine: $1 \: 2 \: 3 \: 4 \: 5 \: 6 \: 7 \: 8 \: 9$