An là học sinh đang học tập tại một trường THPT trên địa bàn.
Để chuẩn bị cho buổi khai giảng năm học mới, An và các bạn thành viên trong CLB Sống Xanh đang tích cực tập duyệt cho màn chào đón các tân học sinh khối 10 nhập học.

Đoàn trường sẽ đánh dấu các vị trí chạy dọc theo tuyến đường từ ngoài cổng vào sân trường thành một hàng.
Hình dung con đường được đánh dấu như một trục số Ox, mỗi vị trí được đánh dấu bởi một số nguyên dương gọi là tọa độ của trục số đó.

CLB có n thành viên được bố trí vào các tọa độ khác nhau, thành viên thứ i đứng ở vị trí có tọa độ nguyên ~a_i~ ~(1 ≤ a_i ≤ 10^9)~ và cầm một bó hoa có màu Đỏ, Vàng, hoặc Trắng để vẫy chào.

Là thành viên được giao nhiệm vụ lưu trữ những bức hình đẹp, An cần tìm một đoạn liên tiếp các bạn trong hàng sao cho:

• Trong đoạn liên tiếp đó, mỗi màu hoa xuất hiện ít nhất một lần.
• Khoảng cách của dãy các thành viên cần chụp được tính bằng hiệu giữa giá trị toạ độ lớn nhất với giá trị toạ độ nhỏ nhất trong tấm hình là nhỏ nhất.

Nếu không tồn tại đoạn nào thỏa mãn, in ra -1.

Input (KHOANGCACH.INP)

• Dòng 1: Số nguyên n (~1 ≤ n ≤ 10^5~)
• n dòng tiếp theo mỗi dòng chứa 2 giá trị:
  
  • Số nguyên ~a_i~ - tọa độ vị trí của học sinh thứ i trên trục số
  • Số nguyên ti – ký hiệu màu hoa mà học sinh thứ i cầm trên tay, trong đó ti = 1 nếu hoa màu Đỏ, ti = 2 nếu hoa màu Trắng, ti = 3 nếu hoa màu Vàng. **Dữ liệu đảm bảo ~a_1 < a_2 < \dots < a_n~.

Output (KHOANGCACH.OUT):

Một số nguyên duy nhất là khoảng cách nhỏ nhất hoặc -1 nếu không tìm được.

Giới hạn

• 60% số test: ~n ≤ 10^3~
• 40% số test: ~10^3 < n ≤ 10^5~

Ví dụ

KHOANGCACH.INP

5
10 1
12 2
13 1
15 3
17 2

KHOANGCACH.OUT

3

Giải thích:
Đoạn từ 12 → 15 có đủ 3 màu, khoảng cách = 15 - 12 = 3 nhỏ nhất.

KHOANGCACH.INP

4
10 1
12 2
13 1
15 2

KHOANGCACH.OUT

-1

Giải thích:
Không có hoa màu vàng → không thể tạo đoạn có đủ 3 màu.