题目描述

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

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

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

输入格式

第一行有一个整数 $N$，以下是一个 $N\times N$ 的方阵，代表各处的高度。$2 ≤ N ≤ 300, 0 ≤ Height ≤ 10000000$。

输出格式

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

2
0 2
1 3

3

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

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

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