Cho bức tường NxN được xây bởi ~\frac{N^{2}}{2}~ viên gạch kích thước ~2 \times 1~. Trên mỗi viên gạch ghi ~2~ số nguyên từ ~1~ đến ~\frac{N^{2}}{2}~.

Bạn hãy phá bức tường trên để tạo thành ~1~ cửa sổ hình vuông thỏa mãn:

• Các cạnh cửa sổ song song với cạnh bức tường
• Cửa sổ không chạm vào cạnh của bức tường
• Phải phá cả viên gạch, không được phá nửa viên gạch
• Cạnh hình vuông lớn nhất

Input

• Dòng ~1~: ~N~ ~(N \leq 2000)~
• Dòng ~2~: ~N~ dòng tiếp theo gồm ~N~ số.

Output

1 số duy nhất là cạnh hình vuông tìm được

Sample Input

6
1 1 4 4 13 14
2 3 3 5 13 14
2 6 7 5 12 12
9 6 7 10 10 15
9 8 8 11 11 15
16 16 17 17 18 18

Sample Output

2

Note

Hình minh họa test ví dụ