Farmer John đã thuê một nhiếp ảnh gia chuyên nghiệp để chụp ảnh một số con bò của mình. Vì đàn bò của FJ thuộc nhiều giống khác nhau, ông muốn bức ảnh có ít nhất một con bò thuộc mỗi giống phân biệt có trong đàn.

\(N\) con bò của FJ đang đứng tại nhiều vị trí trên một đường thẳng; mỗi con được mô tả bởi một vị trí nguyên (tức tọa độ \(x\)) và một mã giống nguyên. FJ dự định chụp một đoạn liên tiếp các con bò dọc theo đường thẳng. Chi phí của bức ảnh bằng kích thước của nó, tức hiệu giữa tọa độ \(x\) lớn nhất và nhỏ nhất của các con bò nằm trong phạm vi bức ảnh.

Hãy giúp FJ tính chi phí nhỏ nhất của một bức ảnh có ít nhất một con bò thuộc mỗi giống phân biệt xuất hiện trong đàn của ông.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bò \(N\) (\(1 \leq N \leq 50\,000\)).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên dương cách nhau bởi dấu cách, lần lượt cho biết tọa độ \(x\) và mã giống của một con bò. Cả hai số đều không quá 1 tỷ.

Dữ liệu ra

In chi phí nhỏ nhất của một bức ảnh chứa mỗi mã giống phân biệt.

Ví dụ

6
25 7
26 1
15 1
22 3
20 1
30 1

4

Nguồn

USACO 2011 November Contest, Silver Division — Cow Lineup. Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=89