描述

农夫约翰（Farmer John）和奶牛贝西（Bessie）正在度过一个“活力十足”的假期。他们整天在山中徒步，到了晚上疲惫不堪时，便返回度假小屋。

由于爬山消耗大量体力且他们已经筋疲力尽，他们希望选择一条最高与最低海拔差值最小的路径返回小屋，无论这条路径有多长。请帮助约翰找到这条易于通行的路径。

山地地图由一个 $N \times N$（$2 \leq N \leq 100$）的整数海拔矩阵表示（海拔范围：$0 \leq \text{任意值} \leq 110$）。约翰和贝西当前位于左上角（第1行第1列），小屋位于右下角（第$N$行第$N$列）。他们可以向上、下、左、右移动，但不能走对角线。

输入

• 第1行：单个整数 $N$
• 第2到$N+1$行：每行包含$N$个整数，表示网格中每个方格的海拔。第2行为网格的第一（顶部）行，第3行为第二行，依此类推。每行的第一个数对应网格的第一（左侧）列。

输出

• 第1行：一个整数，表示最优路径上的最小高度差。

输入样例 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  

来源

USACO 2003 美国公开赛