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.

Yêu cầu

Hãy tìm trên trục số một đ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 ~1~ lần.
• Độ dài đoạn thẳng là nhỏ nhất.

Dữ liệu đầu vào

Gồm ~n + 1~ dòng:

• Dòng 1: Chứa số nguyên dương ~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.

Dữ liệu đầu ra

Gồm 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ì in ra ~-1~.

Ràng buộc dữ liệu

• Có 30% só test thỏa mãn ~1 \le n \le 10^2~;
• Có 30% số test thỏa mãn ~n \le 10^3~;
• Có 40% test thỏa mãn không có ràng buộc gì thêm.

Ví dụ

Ví dụ 1

INPUT

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

OUTPUT

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 ~8 - 4 = 4~ gồm có ~1~ điểm màu xanh, ~2~ điểm màu đỏ, và ~1~ điểm màu vàng.