능선과 계곡

바이트아사르는 언덕에서 트레킹을 즐긴다. 등산을 하는 동안 그는 주변의 모든 능선과 계곡을 둘러본다. 여행을 계획하고 얼마나 걸릴지 가늠하려면, 방문할 지역에 능선과 계곡이 각각 몇 개나 있는지 알아야 한다. 여러분이 그를 도와주자.

바이트아사르는 다음 탐험 지역의 지도를 건네준다. 지도는 $n \times n$ 크기의 정사각형이다. 정사각형에 속하는 각 칸 $(i, j)$ (단, $i, j \in \{1, \dots, n\}$)마다 높이 $w(i, j)$가 주어진다.

두 칸이 변 또는 꼭짓점을 공유하면 서로 인접한다고 한다. 즉, 칸 $(i, j)$는 $(i-1, j-1)$, $(i-1, j)$, $(i-1, j+1)$, $(i, j-1)$, $(i, j+1)$, $(i+1, j-1)$, $(i+1, j)$, $(i+1, j+1)$ 중 지도 안에 있는 칸들과 인접한다.

칸들의 집합 $S$가 다음 조건을 모두 만족하면 능선(각각 계곡)을 이룬다고 한다.

• $S$에 속한 모든 칸의 높이가 같다.
• $S$는 연결되어 있다. 즉, $S$의 어떤 칸에서 출발하더라도 $S$를 벗어나지 않고 인접한 칸으로만 이동하여 $S$의 다른 어떤 칸에도 도달할 수 있다.
• $S$에 속한 모든 칸 $s$와, $s$에 인접하면서 $S$에 속하지 않는 모든 칸 $s'$에 대하여, 능선이면 $w_s > w_{s'}$가, 계곡이면 $w_s < w_{s'}$가 성립한다.

특히 지도의 모든 칸의 높이가 같다면, 그 칸 전체는 능선인 동시에 계곡을 이룬다.

지도가 나타내는 지형에서 능선의 개수와 계곡의 개수를 구하여라.

첫째 줄에 지도의 크기를 나타내는 정수 $n$ ($2 \le n \le 1000$)이 주어진다. 이어지는 $n$개의 줄에는 지도의 각 행이 순서대로 주어진다. $i + 1$번째 줄 (단, $i \in \{1, \dots, n\}$)에는 $i$번째 행에 속한 칸들의 높이 $w(i, 1), \dots, w(i, n)$ ($0 \le w(i, j) \le 10^9$)이 공백 하나로 구분되어 주어진다.

한 줄에 두 정수를 공백 하나로 구분하여 출력한다. 지도가 나타내는 지형에서 능선의 개수와 계곡의 개수를 차례대로 출력한다.

위 그림에서 능선은 실선으로, 계곡은 점선으로 표시되어 있다.