Cho một bản đồ kích thước ~N.N~, mỗi ô mang giá trị ~h[i][j]~ là độ cao của ô đó. ~Jayce~ đang đứng ở ô trên trái ~(1, 1)~ và muốn đi đến cabin ở ô ~(N, N)~. Biết rằng ~Jayce~ có thể đi sang các ô ~(i, j+1)~, ~(i, j-1)~, ~(i-1,j)~, ~(i+1,j)~. Hãy giúp ~Jayce~ tìm đường đi sao chênh lệnh giữa ô có độ cao lớn nhất và ô có độ cao nhỏ nhất là nhỏ nhất có thể.

Input

-Dòng đầu tiên là số nguyên ~N(2 <= N <= 100)~.

-~N~ dòng tiếp theo mỗi dòng gồm ~N~ số, số thứ j của dòng i là độ cao ~h[i][j](1 <= h[i][j] <=100)~.

Output

-Một số nguyên là chênh lệch độ cao nhỏ nhất.

Ví dụ:

Input

4
41 58 53 46
56 58 39 37
49 51 52 53
38 44 34 37

Output

19