Vaellus

• Time limit: 4.00 s
• Memory limit: 512 MB

Eräänä sunnuntaina Uolevi, Maija ja Kaaleppi lähtivät pitkälle vaellukselle vuoristoon. Heidän reittinsä muodostuu peräkkäisistä suorista vuorenseinämistä, ja he kulkevat vasemmalta oikealle.

Tehtäväsi on selvittää jokaisesta seinämästä, minkä seinämän vaeltajat näkevät edessään. Toisin sanoen: kun seinämästä lähtee sen suuntainen suora eteenpäin, mikä on ensimmäinen seuraava seinämä, jonka jokin piste on tämän suoran yläpuolella?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: seinämien kärkipisteiden määrä reitillä. Seinämät on numeroitu kokonaisluvuin $1,2,\ldots,n-1$.

Tämän jälkeen syötteessä on $n$ kokonaislukuparia: seinämän kärkipisteen x- ja y-koordinaatit. Kärkipisteet on annettu kasvavassa x-järjestyksessä.

Tuloste

Ohjelmasi tulee tulostaa $n-1$ kokonaislukua: jokaisesta seinämästä tieto, minkä seinämän vaeltajat näkevät. Jos he eivät näe mitään seinämää, tulosta 0.

Rajat

• $2 \le n \le 10^5$
  
• $0 \le x,y \le 10^9$
  

Esimerkki

Syöte:
8
0 0
3 7
6 2
9 4
11 2
13 3
17 13
20 7

Tuloste:
0 3 6 5 6 0 0