Ridges and Valleys

Byteasar loves trekking in the hills. During his hikes he explores all the ridges and valleys nearby. To plan his journey, he needs to determine how many ridges and valleys are in the region he will visit. You are given a map of the area in the shape of an \( n \times n \) square. For each field \( (i,j) \) (with \( 1\le i,j\le n \)), its height \( w_{(i,j)} \) is provided.

Two fields are adjacent if they share a common side or a common vertex (i.e. the field \( (i,j) \) is adjacent to the fields \( (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) \), provided these fields exist on the map).

A set of fields \( S \) forms a ridge (or a valley) if:

• All fields in \( S \) have the same height.
• The set \( S \) is connected, meaning that from any field in \( S \) one can reach any other field in \( S \) by moving between adjacent fields that are all in \( S \).
• For every field \( s\in S \) and every field \( s'\notin S \) adjacent to \( s \), it holds that \( w_s > w_{s'} \) (for a ridge) or \( w_s < w_{s'} \) (for a valley).

In particular, if all fields on the map have the same height, they form both a ridge and a valley. Your task is to determine the number of ridges and valleys in the landscape described by the map.

inputFormat

The first line contains a single integer \( n \) (\( 1\leq n \leq 1000 \)) representing the size of the square map. The next \( n \) lines each contain \( n \) integers. The \( j \)th integer on the \( i \)th line is \( w_{(i,j)} \), the height of the field at position \( (i,j) \).

outputFormat

Output two integers separated by a space. The first integer denotes the number of ridges and the second integer denotes the number of valleys in the map.

sample

1
5

1 1