题目描述

给定一个 $N$ 行 $N$ 列的方格，第 $i$ 行第 $j$ 列的方格坐标为 $(i, j)$，高度为 $H_{i,j}$。小蓝从左上角坐标 $(0, 0)$ 出发，目的地是右下角坐标 $(N − 1, N − 1)$。 当小蓝位于第 $r$ 行第 $c$ 列时，他有如下的移动方式：

1. 若 $r + 1 < N$，可以移动到 $(r + 1, c)$，花费 $1$ 秒；
2. 若 $c + 1 < N$，可以移动到 $(r, c + 1)$，花费 $1$ 秒；
3. 对于任意整数 $L$，若 $H_{r,c} > H_{r,c+1} > \cdots > H_{r,c+L}$，可以移动到 $(r, c + L)$，花费 $1$ 秒；
4. 对于任意整数 $L$，若 $H_{r,c} > H_{r,c−1} > \cdots > H_{r,c−L}$，可以移动到 $(r, c − L)$，花费 $1$ 秒。

现在给出方格，请问小蓝从 $(0, 0)$ 移动到 $(N − 1, N − 1)$ 最少需要多少秒？

输入格式

输入的第一行包含一个整数 $N$ 表示方格大小。 接下来 $N$ 行，每行包含 $N$ 个整数，表示每个方格上的数字。

输出格式

输出一个整数表示答案。

4
0 1 9 3
2 9 3 7
8 4 8 9
9 8 0 7

5

提示

对于 $20\%$ 的评测用例，$1 \le N \le 10$；

对于 $50\%$ 的评测用例，$1 \le N \le 100$；

对于所有评测用例，$1 \le N \le 1000,0 \le H_{i, j} \le 100$。

样例解释

移动顺序为：$(0, 0)\rightarrow (1, 0)\rightarrow(2, 0)\rightarrow(3, 0)\rightarrow(3, 2)\rightarrow(3, 3)$，其中坐标 $(3, 0),(3, 1),(3, 2)$ 处的数字分别为 $9 > 8 > 0$，所以可以花费 $1$ 秒从 $(3, 0)$ 移动到 $(3, 2)$。