题目描述

一座山的地图用一个 $N × N$ 的方阵给出，每个格子中有一个整数 $h_{i,j}$ ，表示这个格 子的海拔。

现在需要从地图左上角 (第 $1$ 行，第 $1$ 列)，走到地图的右下角 (第 $N$ 行，第 $N$ 列)， 可以向上走、向下走、向右走、向左走，但是不能穿越对角线。

找出一条最高点和最低点高度差最小的路径，输出该路径上最高点和最低点的高度 差。

输入格式

第一行输入一个单独的整数 $N$ ，接下来输入 $N × N$ 的矩阵;

输出格式

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

样例 1 输入

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

样例 1 输出

2

数据范围

对于 $100\%$ 的数据满足:$N ≤ 100, h_{i,j} ≤ 110$