- 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.