问题描述

给定一个 $N$ 行 $N$ 列的方格，第 $i$ 行第 $j$ 列的方格坐标为 $(i,j)$，高度为 $H_{i,j}$。小蓝从左上角坐标 $(0,0)$ 出发，目的地是右下角坐标 $(N−1,N−1)$。

当小蓝位于第 $r$ 行第 $c$ 列时，他有如下的移动方式:

• 若 $r+1<N$，可以移动到 $(r+1,c)$，花费 $1$ 秒;
• 若 $c+1<N$，可以移动到 $(r,c+1)$，花费 $1$ 秒;
• 对于任意整数 $L$，若 $H_{r,c}>H_{r,c+1}>⋯>H_{r,c+L}$​，可以移动到 $(r,c+L)$，花费 $1$ 秒;
• 对于任意整数 $L$，若 $H_{r,c}>H_{r,c−1}>⋯>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

样例说明

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

评测用例规模与约定

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

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

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