Flores


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 64M

Authors:
Problem type
Allowed languages
Ada, BrainF***, C, C#, C++, Dart, Go, Java, JS, Kotlin, Lua, Prolog, Python, Swift, VB

On a faraway planet, strange plants with two stems can be found. Every plant on the planet can be described by three numbers: the x-coordinates of the stems L and R, and the height H at which the stems are connect. The image depicts a plant with L=2, R=5 and H=4.

descripción aqui

Every day a new plant grows on the planet. The plant that grows on day 1 is of height 1, and every subsequent plant is one higher than the previous one.

When a stem of a new plant intersects the horizontal segment of another plant, a small flower grows (if one wasn't there already). If segments merely touch in a point, a flower will not grow there. The following images are a visualization of the first example.

descripción aqui

Write a program that, given the coordinates of all plants, calculates the number of new flower every day.

Input

The first line contains an integer N (1 \le N \le 100 000), the number of days.

Each of the following N lines contains two integers L and R (1 \le L < R \le 100 000), the coordinates of the stems of a plant.

Output

Output N lines, the number of new flowers after each plant grows.

Example 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

Comments


  • -1
    Osnielfc_07  commented on July 12, 2021, 4:04 a.m.

    Brother cogiste mas de 60 pts porque los primeros casos de pruebas estan faciles y se les puede raspar bastante con Force Brute , pero para coger 100 pts tienes que tirar un ( ABI con Deferent Array ) o un ( Segment - tree con Lazy Propagation ). Si el tipo de problema es de Segment - tree es porque la solucion oficial es con este algoritmo.


  • -3
    elpro204  commented on July 9, 2021, 10:42 p.m.

    Dice ser un problema de Segment Tree... pero no le apliqué eso y me salí con mas de 60 puntos ?


  • 2
    Primervirgen  commented on Oct. 5, 2020, 3:56 p.m.

    Muchas gracias a todos por la ayuda ✌?


  • 1
    Sekai02  commented on Oct. 4, 2020, 2:10 p.m.

    El usuario Primervirgen no puede hacer comments en ningun problema, lo cual impide preguntar cualquier duda al resolver un ejercicio, si esto se le impuso como penalizacion por algun comentario ofensivo ya deberia haber cumplido su tiempo, ya que en la mayoria de sitios esto dura 48h. Si alguno de los admin lee esto por favor que se le remueva esta penalizacion, la presencia de la pagina o su orgullo no es mas importante que resolver problemas y promover el movimiento :)


    • 2
      josed  commented on Oct. 4, 2020, 8:14 p.m.

      Ese usuario fue penalizado por incumplir en reiteradas ocasiones los términos del sitio, recomendamos a todos una vez más que los lean. Si él lo desea debe enviar un correo a las direcciones de contacto del sitio para que los administradores reevalúen la penalización y le den una respuesta.


      • 2
        Sekai02  commented on Oct. 5, 2020, 12:59 a.m.

        Gracias por responder, espero que se pueda solucionar el problema.