Grid Descending Moves

You are given an \(N \times N\) grid. The cell in the \(i\)-th row and \(j\)-th column has a height \(H_{i,j}\). Little Blue starts at the top-left cell \((0,0)\) and wants to reach the bottom-right cell \((N-1,N-1)\).

When Little Blue is at cell \((r,c)\), he can move in the following ways (each costing 1 second):

1. If \(r+1 < N\), he can move down to \((r+1, c)\).
2. If \(c+1 < N\), he can move right to \((r, c+1)\).
3. For any positive integer \(L\), if \[ H_{r,c} > H_{r,c+1} > \cdots > H_{r,c+L} \] then he can jump to \((r, c+L)\).
4. For any positive integer \(L\), if \[ H_{r,c} > H_{r,c-1} > \cdots > H_{r,c-L} \] then he can jump to \((r, c-L)\).

Your task is to determine the minimum number of seconds required for Little Blue to move from \((0, 0)\) to \((N-1, N-1)\).

inputFormat

The first line contains an integer \(N\) representing the size of the grid. Each of the next \(N\) lines contains \(N\) integers, where the \(j\)-th integer on the \(i\)-th line denotes \(H_{i,j}\). All numbers are separated by spaces.

outputFormat

Output a single integer: the minimum number of seconds required for Little Blue to reach \((N-1, N-1)\). If it is impossible, output -1.

sample

3
5 4 3
6 3 2
7 3 1

3