MOG
Spanish
|
English

Matcom Online Grader

II Copa UH

Ended

D - Dibujo de Fito

Languages: C, C++, Java, Pascal, Haskell, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)

Para el campeón de la II Copa UH Fito está preparando un dibujo, pero lo único que él sabe pintar son rectángulos y pequeños círculos. Fito pinta $N$ rectángulos en orden. El $i$-ésimo rectángulo ($1 \leq i \leq N$)  tendrá coordenada inferior izquierda $(L_i, 0)$ y coordenada superior derecha $(R_i, i)$.

Cuando el pinta un rectángulo este puede intersectar rectángulos previamente dibujados. Cada vez que Fito pinta un rectángulo, él marca con pequeños círculos las nuevas intersecciones que no había pintado antes. Si un lado del rectángulo se superpone con el lado de otro rectángulo, esto no genera intersecciones.

El problema que hay que resolver es contar, cada vez que Fito pinte un rectángulo, la cantidad de círculos que tiene que añadir.

Input

La primera línea de la entrada tendrá un entero $1 \leq N \leq 10^5$ que indica la cantidad de rectángulos que Fito va a pintar. En cada una de las $N$ siguientes línea habrá dos enteros $1 \leq L_i \lt R_i \leq 10^5$ que definen el $i$-ésimo rectángulo.

Output

La salida debe contener $N$ líneas. En la $i$-ésima línea debe haber un entero que represente la cantidad de círculos nuevos que Fito debe pintar después de insertar el $i$-ésimo rectángulo.

Sample test(s)

Input
4 1 4 3 7 1 6 2 6
Output
0 1 1 2
Input
5 1 3 3 5 3 9 2 4 3 8
Output
0 0 0 3 2