CSES - Lomamökki
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Sinulla on lomamökki, jota vuokraat asiakkaille. Tiettynä päivänä mökissä voi olla enintään yksi asiakas.

Luoksesi tulee tietyssä järjestyksessä nn asiakasta, joista jokainen haluaa vuokrata mökin päivästä aa päivään bb. Kuka on ensimmäinen asiakas, jonka toivomusta et pysty toteuttamaan?

Huomaa, että jos asiakas poistuu mökistä päivänä kk, seuraava asiakas voi saapua aikaisintaan päivänä k+1k+1.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: asiakkaiden määrä. Asiakkaat on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

Sitten syötteessä on nn riviä, joista jokaisella on kaksi kokonaislukua aa ja bb: asiakas haluaa vuokrata mökin päivästä aa päivään bb.

Tuloste

Tulosta yksi kokonaisluku: ensimmäinen asiakas, jonka toivomusta et voi toteuttaa. Jos voit toteuttaa kaikki toivomukset, tulosta kuitenkin 1-1.

Rajat

  • 1n51051 \le n \le 5 \cdot 10^5
  • 1ab1091 \le a \le b \le 10^9

Esimerkki 1

Syöte:

4
2 5
8 9
3 7
12 15

Tuloste:

3

Selitys: Asiakas 3 haluaa vuokrata mökin päivästä 3 päivään 7. Tämä ei kuitenkaan onnistu, koska asiakas 1 on jo vuokrannut mökin päivästä 2 päivään 5.