Pe mare va avea loc o mare bătălie între N vapoare. Vapoarele sunt considerate nişte puncte şi sunt date prin coordonatele lor carteziene x şi y. Din motive greu de înţeles, vapoarele nu pot ataca decât vapoarele care se află la stânga şi mai jos (mai exact, un vapor la poziţia x1, y1 poate ataca alt vapor la poziţia x2, y2 dacă şi numai dacă x1 > x2 şi y1 > y2). Pentru că această bătălie are loc în zona Triunghiului Bermudelor, vapoarele apar (se teleportează) pe rând în zona bătăliei. Vapoarele sunt numerotate 1, 2, ..., N în ordinea apariţiei lor. În momentul în care un vas apare, dacă există alt vas care a apărut deja şi care poate să îl atace pe cel nou, vasul nou este distrus instantaneu. Dacă nu, vasul cel nou rămâne pe mare şi distruge toate vasele pe care le poate ataca.
Cerinţă
Dându-se coordonatele la care apar pe rând vapoarele, să se afle pentru fiecare vapor dacă este distrus sau nu în momentul apariţiei sale şi dacă nu este distrus, să se precizeze numărul total de vapoare rămase pe mare după apariţia sa.
Date de intrare
Pe prima linie a fişierului de intrare sea2.in se află numărul natural N reprezentând numărul de vapoare ce vor apărea pe mare. Pe fiecare dintre următoarele N linii se află câte o pereche de numere întregi separate printr-un spaţiu, reprezentând coordonata x respectiv y a vaporului corespunzător liniei (mai exact, pe linia i sunt scrise coordonatele vaporului i-1, pentru orice i de la 2 la N+1).
Date de ieşire
Fişierul de ieşire sea2.out va conţine N linii, fiecare linie cu un număr întreg. Pe linia i se va afla -1 dacă vaporul i este distrus în momentul apariţiei, sau un număr întreg strict pozitiv reprezentând numărul de vapoare de pe mare după apariţia vaporului i în caz contrar.
Restricţii
• 1 ≤ N ≤ 200000 (două sute de mii)
• Coordonatele sunt numere întregi strict pozitive mai mici sau egale cu 260000
• Nu vor exista două vase cu aceeaşi coordonată x sau cu aceeaşi coordonată y.
Exemple
sea2.in
sea2.out
Explicaţii
5
4 1
8 6
7 5
3 4
9 3
1
1
-1
-1
2
Vaporul 1 rămâne pe mare
Vaporul 2 rămâne pe mare şi distruge vaporul 1
Vaporul 3 este distrus de vaporul 2
Vaporul 4 este distrus de vaporul 2
Vaporul 5 rămâne pe mare, împreună cu vaporul 2