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ä n asiakasta, joista jokainen haluaa vuokrata mökin päivästä a päivään b. Kuka on ensimmäinen asiakas, jonka toivomusta et pysty toteuttamaan?

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

Syöte

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

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

Tuloste

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

Rajat

  • 1 \le n \le 5 \cdot 10^5
  • 1 \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.