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.