treap

Treap

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

Undeva intr-un univers paralel, Piromanul a ajuns sa iubeasca apa si nu focul ca de obicei. Totusi, nu s-a schimbat prea mult... inca ii plac treapurile, ca in problema Metro. Gandindu-se ca comisia A.G.M s-ar face de ras daca ar lasa sa treaca cea de-a treia editie fara o problema cu treapuri, s-a gandit sa aibe grija de imaginea tuturor colegilor sai.

Undeva intr-un univers paralel, Piromanul a ajuns sa iubeasca apa si nu focul ca de obicei. Totusi, nu s-a schimbat prea mult... inca ii plac treapurile, ca in problema 'Metro':http://www.infoarena.ro/problema/metro . Gandindu-se ca comisia A.G.M s-ar face de ras daca ar lasa sa treaca cea de-a treia editie fara o problema cu treapuri, s-a gandit sa aibe grija de imaginea tuturor colegilor sai.

Piro, baiat fin de altfel, nu isi doreste sa fie chiar cel mai antipatizat membru al comisiei, asa ca va face o scurta incursiune impreuna cu voi in ceea ce inseamna **tainele treap-ului**.

**Un treap** este un arbore cu proprietatea ca fiecare nod are asociat doua valori : cheie si prioritate. Daca ne uitam doar la cheile nodurilor, facand abstractie de prioritati, atunci acesta este **arbore binar de cautare**. Daca ne uitam la prioritatile nodurilor, facand abstractie de chei, atunci acesta este **max-heap**.

Dandu-vi-se un arbore binar cu $N$ noduri, inradacinat in nodul $1$, trebuie sa calculati cati subarbori exista cu proprietatea de **treap**.

Dandu-vi-se un arbore binar cu $N$ noduri, inradacinat in nodul $1$, trebuie sa determintati care subarbori au proprietatea de **treap**.

h2. Date de intrare

h2. Restricţii

* **$1 <= N <= 150,000$**
* **$1 <= KEY[~i~] <= 10^9^$**
* **$1 <= PRIO[~i~] <= 10^9^$**

* $1 <= N <= 150.000$
* $1 <= KEY[~i~] <= 10^9^$
* $1 <= PRIO[~i~] <= 10^9^$

* **Arborele se considera ca este inradacinat in nodul $1$**
* **La finalul fisierului de iesire este $'\n'$, nu spatiu**
* **Un subarbore inradacinat intr-un nod care nu are fii, este considerat frunza si reprezinta evident un treap**

* Nu se garanteaza ca prioritatile generate sunt aleatoare, treap-ul avand forme dintre cele mai diverse.

h2. Exemplu