题目描述

魔沼蛙有很强的跳跃能力，上个版本的时候击杀魔沼蛙后能回复大量的血量和法力，所以 $\mathcal{Rubyonly}$ 非常喜欢刷，但是因为这个版本不提供回复了，$\mathcal{Rubyonly}$ 就不爱刷了，除非告诉他魔沼蛙的最长逃跑路线，他就知道要买几速的鞋子去追击了。

魔沼蛙的逃跑是在一个 $n\times n$ 的格子图上，每个格子都有固定的高度 $a_{i,j}$，它会随机从某一个格子上开始逃跑，每步只会跳往上下左右四个格子中高度大于当前格子高度的格子，且不会跳出这个格子图，一直跳到不能跳为止。

现在 $\mathcal{Rubyonly}$ 想知道魔沼蛙可能的最长逃跑路线长度。

输入格式

从文件 frog.in 中读入数据。

第 $1$ 行一个整数 $n$。

第 $2\sim n + 1$ 行，每行 $n$ 个整数，表示每个格子的高度 $a_{i,j}$。

输出格式

输出到文件 frog.out 中。

一行一个整数，表示魔沼蛙可能的最长逃跑路线长度。

3
1 2 3
6 5 4
7 8 9

9

数据范围

对于 $10\%$ 的数据，保证 $n = 1$；

对于 $40\%$ 的数据，保证 $n \leq 10$；

对于 $100\%$ 的数据，保证 $1\leq n\leq 10^3, 0\leq a_{i,j}\leq 10^6$。