Trên trục \(Ox\) cho \(n\) điểm đánh số từ \(1\) đến \(n\), điểm thứ \(i\) ở vị trí có tọa độ là \(x_i(1 \leq i \leq n)\). Mỗi điểm được tô một trong \(3\) màu xanh, đỏ, vàng. Hãy tìm trên trục một số đoạn thẳng thỏa mãn hai điều kiện sau:

• Trong đoạn thẳng đó mỗi màu xuất hiện ít nhất một lần.
• Độ dài đoạn thẳng là nhỏ nhất.

Dữ liệu

Vào từ file văn bản PPOINT.INP:
- Dòng đầu tiên chứa số nguyên \(n(1 \leq n \leq 10^6).\)
- \(n\) dòng tiếp theo, mỗi dòng chứa hai giá trị \(x_i,m_i\):
-Số nguyên \(x_i\) là tọa độ của điểm thứ \(i\) trên trục số \((1 \leq x_i \leq 10^9, 1 \leq i \leq n)\).
-Số nguyên \(m_i\) là ký hiệu màu của các điểm, trong đó \(m_i=1\) là màu xanh, \(m_i=2\) là màu đỏ, \(m_i=3\) là màu vàng.

Kết quả

Ghi ra file văn bản PPOINT.OUT một số là độ dài đoạn thẳng thỏa mãn yêu cầu bài toán, nếu không tìm thấy đoạn thẳng nào thỏa mãn yêu cầu thì ghi ra giá trị \(-1\).

Ràng buộc

• Có \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn \(1\leq n \leq 10^2\)
• \(30\%\) số test ứng với \(30\%\) số điểm thỏa mãn \(n \leq 10^3\)
• \(40\%\) số test ứng với \(40\%\) số điểm không ràng buộc gì thêm.

6
2 1
4 1
5 2
7 2
8 3
10 3

4