- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
میدانیم یه قل دو قل جایگاه ویژهای در میان اهالی برره دارد.
این بازی در برره به شکل عجیبی انجام میشود. بر روی یک خط \(n\) سنگ قرار میگیرد که روی سنگ \(i\)اُم عدد \(a_i\) نوشته شده و در موقعیت \(x_i\) قرار دارد.
به ازای هر بازهای از خط(بازهای از \(x\)ها)، تعداد اعداد متمایزی که روی سنگهای داخل این بازه نوشته شدهاست را درجهی الدنگی آن بازه مینامیم. شما باید بین همهی بازههایی که درجهی الدنگی آنها بیشینه است کوتاهترین (یعنی بازهای که انتها منهای ابتدایش کمینه است) آنها را پیدا کنید و طول آن را چاپ کنید.
ورودی
در خط اول \(n\)، تعداد سنگها آمده است. در هر یک از \(n\) خط بعد در خط \(i\) به ترتیب \(x_i\) و \(a_i\) آمده است. همهی \(x_i\)ها متمایز اند. \[1 \le n \le 50\ 000\] \[1 \le a_i, x_i \le 10^9\]
خروجی
طول کوتاهترین بازه با درجه الدنگی بیشینه را چاپ کنید.
مثال
ورودی نمونه ۱
6
25 7
26 1
15 1
22 3
20 1
30 1
خروجی نمونه ۱
4
بازهی ۲۲ تا ۲۶ (با طول ۴) جواب است. درجهی الدنگی این بازه ۳ است و طول آن برابر ۴. درجهی الدنگی آن بیشینه است و طول آن بین تمام بازههایی که درجهی الدنگی آنها بیشینه است کمینه است.