约翰和牛贝茜享受了最有趣的假期。他们花了一整天在山上漫步，最后疲惫地回到他们假日的小屋。

由于爬山需要很多体力，而且他们已经非常疲惫，所以他们想要穿过一条最高点和最低点高度差最小的路径回到他们的小屋，尽管这样的路径或许很长。请帮助约翰找到这样一条易于攀登的路线！

整座山的地图用一个 $N\times N$的方阵给出，每个格子中有一个整数$h_{i,j}$，表示这个格子的海拔。约翰和贝茜现在在地图左上角(第$1$行，第$1$列)，而小木屋在地图的右下角(第 $N$ 行，第 $N$ 列)，他们可以向上走、向下走、向右走、向左走，但是不能穿越对角线。

输入格式

第一行输入一个单独的整数 $N$，接下来输入 $N\times N$ 的矩阵；

输出格式

共一行一个整数，表示路径上最高点和最低点的高度差。

样例

样例输入

5
1 1 3 6 8
1 2 2 5 5
4 4 0 3 3
8 0 2 3 4
4 3 0 2 1

样例输出

2

数据范围与提示

• 对于$100$%的数据，$N\le 100,h_{i,j}\le 110$
• 时间限制：$1000\mathrm{ms}$
• 空间限制：$131072\mathrm{KB}$

大样例下载

百度网盘大样例下载 提取码: GFOI

阿里云盘大样例下载

夸克云盘大样例下载