该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

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

整座山的地图用一个 $N*N (2 ≤ N ≤ 100)$ 的方阵给出. 方阵中填充了一些描述海拔的整数 $(0 ≤ 任意高度 ≤ 110)$ . 约翰和贝茜现在在地图的左上角 (第一行, 第一列) 而小木屋在地图的右下角 (第N行, 第N列). 他们可以向上走, 向下走, 向右走, 向左走, 但是不能穿越对角线.

输入输出格式

输入格式

第1行输入一个单独的整数 $N$, 接下来输入 $N*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