Problem D
Cave Exploration

Source: Photo by macg on pixabay

It is monsoon season, and your goldfish Orange is stuck at the bottom of a cave system in Thailand. Every hour, the water rises by $1$ meter. Thankfully, Orange has the ability to swim instantaneously from one location to another. However, he can’t hop over the sharp rocks in the way.

You trust that Orange is smart and will find the way out of the cave as soon as possible. To prepare Orange’s meal, you want to write a program to find out how long it will take for Orange to come back home.

You are given the cave system as an $N \times N$ grid where each location $(i, j)$ contains a nonnegative integer, $h_{i, j}$, representing the height of the rocks in meters at that location. Orange can only swim left, right, up, or down from one submerged location to another submerged location (but not diagonally).

A location $(i, j)$ is submerged if the water level is at least $1$ meter higher than $h_{i, j}$. Orange’s starting location will always be at $(0, 0)$, with $h_{0, 0} = 0$. The initial water level is $1$ meter so that Orange’s start location is submerged. The only exit in the cave is at location $(N - 1, N - 1)$. After how many hours can Orange find his way to the exit?

Input

The input consists of one integer, $N$, on the first line such that $2 \leq N \leq 100$, followed by $N$ lines with $N$ integers each, separated by spaces, such that each integer represents the height $h_{i, j}$ ($0 \le h_{i, j} \le 10^8$) of the rocks at location $(i, j)$.

Output

Output a single integer, which is the minimum number of hours that must pass before Orange can reach the exit.

2
0 3
2 4

4

5
0 2 3 10 4
10 23 2 21 12
11 10 12 12 16
12 12 18 10 10
10 10 10 11 10

12