Ridges and Valleys

Byteasar loves trekking in the hills. During his hikes he explores every ridge and valley nearby. To plan a trip and know how long it will take, he needs to know how many ridges and how many valleys lie in the area he is about to visit. Your job is to help him.

Byteasar gives you a map of his next expedition. The map is an $n \times n$ square. For every field $(i, j)$ of the square (with $i, j \in \{1, \dots, n\}$) its height $w(i, j)$ is given.

Two fields are adjacent when they share a side or a corner. In other words, field $(i, j)$ is adjacent to $(i-1, j-1)$, $(i-1, j)$, $(i-1, j+1)$, $(i, j-1)$, $(i, j+1)$, $(i+1, j-1)$, $(i+1, j)$ and $(i+1, j+1)$, whenever those fields still lie on the map.

A set of fields $S$ forms a ridge (respectively a valley) when:

• all fields in $S$ have the same height,
• $S$ is connected, that is, from any field in $S$ you can reach any other field in $S$ by stepping only between adjacent fields without ever leaving $S$,
• for every field $s \in S$ and every field $s' \notin S$ adjacent to $s$, the heights satisfy $w_s > w_{s'}$ (for a ridge) or $w_s < w_{s'}$ (for a valley).

In particular, if every field on the map has the same height, all of them together form both a ridge and a valley.

Determine the number of ridges and the number of valleys in the landscape described by the map.

The first line contains one integer $n$ ($2 \le n \le 1000$), the size of the map. Each of the next $n$ lines describes one row of the map: line $i + 1$ (for $i \in \{1, \dots, n\}$) contains $n$ integers $w(i, 1), \dots, w(i, n)$ ($0 \le w(i, j) \le 10^9$), separated by single spaces, the heights of the fields in row $i$.

Print a single line with two integers separated by one space: the number of ridges followed by the number of valleys in the landscape described by the map.

In the figures above the ridges are drawn with a solid line and the valleys with a dashed line.