문제

민용이는 독특한 방식으로 그림을 그리는 화가로 전 세계적인 주목을 받고 있다.

민용이는 $N \times N$ 격자 모양의 빈 캔버스에서 작업을 시작한다. 격자의 각 칸이 $0$인 것은 아직 색이 칠해지지 않았음을 의미한다. 민용이는 $1$부터 $N^2$까지 번호가 매겨진 $N^2$가지 색상을 사용하여 캔버스에 각각 정확히 하나의 사각형을 그린다. 예를 들어, 민용이가 색상 $2$로 사각형을 먼저 그리면 캔버스는 다음과 같은 상태가 될 수 있다.

2 2 2 0
2 2 2 0
2 2 2 0
0 0 0 0

그다음 색상 $7$로 사각형을 그리면 다음과 같이 변할 수 있다.

2 2 2 0
2 7 7 7
2 7 7 7
0 0 0 0

마지막으로 색상 $3$으로 작은 사각형을 그리면 다음과 같아질 수 있다.

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

각 사각형의 변은 캔버스의 테두리와 평행하며, 사각형의 크기는 최소 칸 하나부터 최대 캔버스 전체 크기까지 가능하다. 민용이는 $1$부터 $N^2$까지의 모든 색상을 정확히 한 번씩 사용하며, 나중에 칠해진 색상은 이전에 칠해진 색상의 일부 또는 전부를 완전히 덮을 수 있다.

최종적으로 완성된 캔버스의 상태가 주어졌을 때, $N^2$가지 색상 중 가장 첫 번째로 칠해졌을 가능성이 있는 색상의 개수를 구하시오.

입력

첫째 줄에 캔버스의 크기 $N$이 주어진다. ($1 \le N \le 1\,000$)

이어서 $N$개의 줄에 걸쳐 최종 캔버스의 상태를 나타내는 $N$개의 정수가 공백으로 구분되어 주어진다. 각 정수는 $0$ 이상 $N^2$ 이하의 범위를 갖는다. 입력으로 주어지는 상태는 문제의 설명대로 $N^2$개의 색상 사각형을 순서대로 칠하여 만들 수 있음이 보장된다.

출력

가장 첫 번째로 칠해졌을 가능성이 있는 색상의 개수를 출력한다.

예제 입력 1

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

예제 출력 1

14