Picowso's First Color

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

Picowso paints in a very particular way. She starts with an \(N \times N\) blank canvas, represented by an \(N \times N\) grid of zeros, where a zero indicates an empty cell of the canvas. She then draws \(N^2\) rectangles on the canvas, one in each of \(N^2\) colors (conveniently numbered \(1 \ldots N^2\)). Each rectangle has sides parallel to the edges of the canvas. Later paintings may completely cover up some of the earlier ones.

Given the final state of the canvas, determine how many of the \(N^2\) colors could have possibly been the first painted. The idea is that if a color was painted first then the rectangle it originally painted can be extended to cover all of its visible cells. In other words, if a color is visible then in the minimum bounding rectangle that contains all cells of that color, there must be no cell that is blank (i.e. 0), because Picowso would have painted that cell as well. For colors that do not appear in the final canvas (and are therefore completely covered), it is always possible that they were painted first.

Formally, let the canvas be represented by a matrix \(A\) of size \(N \times N\). For each color \(c\) from \(1\) to \(N^2\):

• If color \(c\) is visible, let \(r_{min}, r_{max}\) be the minimum and maximum rows and \(c_{min}, c_{max}\) the minimum and maximum columns where \(c\) appears. If for every cell \(A[i][j]\) with \(r_{min} \le i \le r_{max}\) and \(c_{min} \le j \le c_{max}\), \(A[i][j] \neq 0\), then color \(c\) could have been painted first.
• If color \(c\) is not visible at all, it could have been painted first.

Your task is to count the number of colors which could have been painted first.

inputFormat

The first line contains an integer \(N\) representing the size of the canvas.

The next \(N\) lines each contain \(N\) integers. The \(j\)-th integer on the \(i\)-th line represents \(A[i][j]\), the color at that cell (with 0 representing a blank).

outputFormat

Output a single integer: the number of colors that could have possibly been the first painted.

sample

4
2 2 3 0
2 7 3 7
2 7 7 7
0 0 0 0

16