Modern Art#10529

Modern Art

1 second

128 megabytes

Hard

Art critics worldwide have only recently begun to recognize the creative genius of the great bovine painter, Picowso.

Picowso paints in a very particular way. She starts with an $n \times n$ n \times n blank canvas, represented by an $n \times n$ n \times n grid of zeros, where a zero indicates an empty cell of the canvas. She then paints $n^{2}$ n^2 rectangles on the canvas, using each of $n^{2}$ n^2 colors exactly once. The colors are conveniently numbered from $1$ to $n^{2}$ n^2.

For example, she might start by painting a rectangle in color $2$ , resulting in the following intermediate canvas:

She might then paint a rectangle in color $7$ :

Finally, she might paint a small rectangle in color $3$ :

Each rectangle has sides parallel to the edges of the canvas, and a rectangle can be as large as the entire canvas or as small as a single cell. Each color from $1$ to $n^{2}$ n^2 is used exactly once, although later colors may completely cover parts of rectangles painted earlier.

Given the final state of the canvas, please determine how many of the $n^{2}$ n^2 colors could have been painted first.

Input

The first line contains the size $n (1 \leq n \leq 1000)$ n~(1 \le n \le 1000) of the canvas. The next $n$ lines describe the final state of the canvas. Each line contains $n$ integers in the range $0$ to $n^{2}$ n^2. The input is guaranteed to have been produced as described above, by painting a sequence of rectangles in distinct colors.

Output

Print the number of colors that could have been painted first.

Examples

In this example, color $2$ could have been painted first. Color $3$ clearly had to be painted after color $7$ , and color $7$ clearly had to be painted after color $2$ . Since we do not see the other colors, we can deduce that any of them could also have been painted first.

Example 1