현대 미술 (플래티넘)

전 세계 미술 평론가들이 위대한 소 화가 피카우소(Picowso)의 창의적인 재능을 이제야 알아보기 시작했다.

피카우소는 아주 독특한 방식으로 그림을 그린다. 처음에는 $N \times N$ 크기의 빈 캔버스로 시작하는데, 이 캔버스는 0으로 채워진 $N \times N$ 격자로 나타내며 0은 캔버스의 빈 칸을 뜻한다. 그다음 캔버스 위에 직사각형 $N^2$개를 그린다. 색은 모두 $N^2$가지이고 편의상 $1$부터 $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 \leq N \leq 1000$)

다음 $N$개의 줄에는 캔버스의 최종 그림이 주어진다. 각 줄에는 $0$ 이상 $N^2$ 이하의 정수 $N$개가 있다. 입력은 위에서 설명한 방식대로, 서로 다른 색의 직사각형을 차례로 칠해서 만들어진 그림임이 보장된다.

가장 먼저 칠해졌을 수 있는 색의 개수를 출력한다.

첫 번째 예제에서 색 2는 가장 먼저 칠해졌을 수 있다. 색 3은 분명히 색 7보다 나중에 칠해졌고, 색 7은 분명히 색 2보다 나중에 칠해졌다. 나머지 색은 그림에 보이지 않으므로 이 색들도 가장 먼저 칠해졌을 수 있다고 추론할 수 있다. 따라서 답은 $16 - 2 = 14$이다.