Problem Statement

You have to reach a location as early as you can and the weather forecast predicts that it will rain heavily today. The surface in front of you has a very unique terrain. Assume it is a N X N surface, each square grid[i][j] represents the height (distance between surface and base) at that point(i, j).Also the boundary of this field is very high.

You have arranged a boat which is very fast. Your boat can cover an infinite distance in zero time. You start at t=0 and the rain starts as soon as you start your journey (at t=0). At time t minutes, the height of the water everywhere is t units.

You can take your boat from a square to another 4-directionally adjacent square (up, down, left, right)
if and only if the elevation of both squares individually are at most t (The boat can only move to a point where the height of surface is below or equal to the water level) Of course, you must stay within the boundaries of the grid during your journey. You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?

Input Format

• N will be given in first line.
• After that N lines follow will having N values each.
Constraints
• 2 <= N <= 50.
• Grid[i][j] is a permutation of [0,..., N*N-1].

Output Format

Print the least time until.

Sample Test case

Sample Input 1

2 
0 2
1 3

Sample Output 1

3

Explanation

02
13
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbours have a higher elevation than 0. You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.

Sample Input 2

5
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6

Sample Output 2

16
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.