Đoạn Liên Tiếp Ngắn Nhất

Trên một đường thẳng có $N$ điểm, mỗi điểm có tọa độ $x_i$ và thuộc loại $t_i$. Cần chọn một đoạn liên tục (theo tọa độ) sao cho chứa ít nhất một điểm thuộc mỗi loại, và độ dài đoạn (hiệu giữa tọa độ lớn nhất và nhỏ nhất) là nhỏ nhất.

Dữ liệu vào

• Dòng 1: Số nguyên $N$
• $N$ dòng tiếp theo: Mỗi dòng chứa hai số nguyên $x_i$ và $t_i$

Dữ liệu ra

• In ra một số nguyên — độ dài đoạn nhỏ nhất chứa đủ mọi loại.

Ràng buộc

• $1\le N\le 50000$
• $1\le x_i,t_i\le {10}^9$

Ví dụ