Masala #1181
Sayyohlar
Robolandiyada M ta ketma-ket bog' mavjud va ular 1 dan M gacha raqamlangan. Bugun Robolandiyaga N ta sayyoh tashrif buyurgan va \(i-\)sayyoh \([A_i:B_i]\) oraliqdagi barcha bog'larni aylanib chiqadi. Agar ikki sayyoh bitta bog'da uchrashib qolishsa, ular do'stlashadi.
Har bir sayyoh uchun kun oxirida do'stlashishi mumkin bo'lgan sayyohlarning maksimal sonini aniqlang.
Kiruvchi ma'lumotlar:
Kirish faylining 1-qatorida ikkita natural son - N va M \((1 \le N \le 2*10^5, 1 \le M \le 10^9)\) kiritiladi.
Keyingi N ta qatorning har birida ikkitadan butun son \(A_i\) va \(B_i \ (1 \le A \le B \le M)\) kiritiladi.
Chiquvchi ma'lumotlar:
Har bir sayyoh uchun alohida qatorda kun oxirida do'stlashishi mumkin bo'lgan sayyohlarning maksimal sonini chop eting.
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
4 5 2 3 1 2 3 4 5 5 |
2 1 1 0 |
Telegram kanalimizga obuna bo'ling