Robotic Skills
Description
Franco is learning robotics and he is very excited because he has already built his first robot. His original plan was for this robot to be able to play Hopscotch, but since this is very difficult, he settles for a simpler version of this game.
On the floor, there is a board with $N \times N$ squares drawn. Each of these squares contains an integer between $1$ and $N^2$. It is also known that there are no repeated numbers. The robot can start its journey at any point outside the board and can only move horizontally and vertically, that is, in directions parallel to the edges of the board. In order to change its direction of movement from vertical to horizontal (or vice versa), the robot must be inside one of the squares. The robot can change its direction at most once in each square. It can never change its direction by $180^\circ$. The journey must end outside the board. Let $c_1, c_2, c_3, \ldots , c_k$ be the numbers written in the squares where the robot changed its direction. For the journey to be valid, it must satisfy $c_1 < c_2 < c_3 < \ldots < c_k$. The score of a journey is the number of squares in which the robot changed its direction. A valid journey on a $3\times 3$ board is shown below:
Help Franco program the robot so that the score of his journey is as high as possible.
The first line contains an integer $N$ $(2 \leq N \leq 1000)$.
Then, the $i$-th of the following $N$ lines contains $N$ integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, N}$, which are the numbers written in the $i$-th row of the board $(1 \leq A_{i, j} \leq N^2)$. It is guaranteed that all numbers are different.
A single line with the maximum score that the robot can achieve in its journey.
Input
The first line contains an integer $N$ $(2 \leq N \leq 1000)$.
Then, the $i$-th of the following $N$ lines contains $N$ integers $A_{i, 1}, A_{i, 2}, \ldots, A_{i, N}$, which are the numbers written in the $i$-th row of the board $(1 \leq A_{i, j} \leq N^2)$. It is guaranteed that all numbers are different.
Output
A single line with the maximum score that the robot can achieve in its journey.
2
1 2
3 4
3
1 4 7
9 8 5
2 6 3
3
5
Note
In the second example, a possible journey of the robot that achieves the maximum score can be found in the image in the problem statement. Note that the robot does not change direction in the squares with the numbers 6 and 9.
Another possible journey that also achieves the maximum score is obtained by changing direction in the squares $1, 2, 3, 5$ and $9$.