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 \le i \le 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 \le n \le 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 \le x_i \le 10^9, 1 \le i \le 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.

Các số trên cùng một dòng cách nhau một dấu cách.

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 \le n \le 10^{2}~.
• ~30\%~ số test khác ứng với ~30\%~ số điểm thỏa mãn ~n \le 10^3~.
• ~40\%~ số test còn lại ứng với ~40\%~ số điểm không ràng buộc gì thêm.

Ví dụ

Dữ liệu

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

Kết quả

4

Giải thích

• Đoạn thẳng từ điểm có tọa độ ~4~ đến điểm có tọa độ ~8~ có độ dài là ~8-4=4~ có ~1~ điểm màu xanh, ~2~ điểm màu đỏ và ~1~ điểm màu vàng.