- Time limit: 1.00 s
- Memory limit: 128 MB
Ravintolassa kävi päivän aikana n asiakasta. Tiedät jokaisesta asiakkaasta, milloin hän saapui ravintolaan ja poistui ravintolasta. Tehtäväsi on selvittää, montako asiakasta ravintolassa oli enimmillään samaan aikaan.
Syöte
Syötteen ensimmäisellä rivillä on kokonaisluku n: asiakasmäärä.
Tämän jälkeen syötteessä on n riviä. Kullakin rivillä on kaksi kokonaislukua a_i ja b_i, kun i=1,2,\ldots,n. Tämä tarkoittaa, että asiakas saapui ravintolaan hetkellä a_i ja poistui ravintolasta hetkellä b_i.
Kullakin ajanhetkellä voi olla vain yksi tapahtuma (asiakas saapuu tai poistuu).
Tuloste
Ohjelmasi tulee tulostaa yksi kokonaisluku: suurin asiakkaiden määrä ravintolassa samaan aikaan.
Rajat
- 1 \le n \le 10^5
- 1 \le a_i \le b_i \le 10^9
Esimerkki
Syöte:
3 4 9 2 3 8 11
Tuloste:
2