题目描述

小$C$在一个排水系统不太好的学校上学。又是一个下雨天，学校里高低不平积了很多水。小$C$突发奇想：如果大雨一直下，多久以后我可以在学校里游泳呢？

学校是 $N x N$的坐标方格 $grid$中，每一个方格的值 $grid(i,j)$表示在位置 $(i,j)$的高度。现在开始下雨了。当时间为$t$时，此时雨水导致方格中任意位置的水位为 $t$。你可以从一个方格游向四周相邻的任意一个方格，但是前提是此时水位必须同时淹没这两个方格。假定小$C$的游动是不耗时的。

现在小$C$从坐标方格的左上$(0,0)$出发。最少耗时多久他才能到达坐标方格的右下平台$(N-1, N-1)$？

输入

第一行有一个整数$N$，以下是一个$N*N$的方阵，代表各处的高度。 输入范围：$2 ≤ N ≤ 300 0 ≤ Height ≤ 10000000$

输出

输出一个整数，代表最少等待时间$T$.

样例1

2
0 2
1 3

3

样例2

5
0 1 2 3 4
24 23 22 21 5
12 13 14 15 16
11 17 18 19 20
10 9 8 7 6

16

提示

样例$1$：时间为$3$时，才可以游向平台$(1,1)$，此时水位为$3$。

样例$2$：时间为$16$时，水位为$16$，此时才能保证$(0,0)$和$(4,4)$是联通的（请自行找出一条通路）。