题目描述

小$\red{TY}$突然想画画，他有独特的艺术风格，他从$\red{N×}$$\red{N}$空白画布开始，其中$\red{0}$表示画布的空单元格。然后他会在画布上绘制恰好矩形，每个颜色是$\red{1}$到$\red{N\times N}$中的一个。他每次可以选择任意一种未使用过的颜色进行绘画。例如，他可以从颜色$\red{2}$的矩形开始，画出这样的画布：

2 2 2 0

2 2 2 0

2 2 2 0

0 0 0 0

然后他可以用颜色$\red7$绘制一个矩形：

2 2 2 0

2 7 7 7

2 7 7 7

0 0 0 0

然后他可以在颜色$\red3$上绘制一个小矩形：

2 2 3 0

2 7 3 7

2 7 7 7

0 0 0 0

每个矩形都平行于画布边缘，而且矩形可以与整个画布一样大或者像一个单元一样小。每个颜色从$\red1$到正好使用一次，后来的颜色可能完全覆盖一些较早画上的颜色。

现在已知画布的最终状态，请计算有多少种颜色可能被第一个被画。

输入格式

输入的第一行包含$\red{n, }$画布的大小 $\red{(1 \leq N \leq 1000).}$

下一个$\red{n}$线条描述了画布的最终图片，每条都包含??范围内的整数$\red{0 \ldots n^2. }$通过用不同颜色绘制连续的矩形，可以保证输入已按上述方式绘制。

输出格式

请输出可以先绘制的颜色数量的计数。

样例

输入样例

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

输出样例

14

提示

在这个例子中，颜色 $\red{2 }$可能是第一个被绘制的。颜色 $\red{3 }$显然必须是在颜色 $\red{7 }$之后绘制的，而颜色 $\red{7 }$显然必须是在颜色 $\red{2 }$之后绘制的。由于我们没有看到其他颜色，因此我们推断它们也可以先绘制。