Valley Regions

Bessie is exploring a square grid of size \(N\times N\) where each cell has a height. Outside the grid the height is treated as \(\infty\). A region is any nonempty set of cells that is edge‐connected (neighbors by up, down, left or right moves). A region is said to be holed if its complement (the cells not in the region together with the infinite outside) is not connected when using point (8-direction) adjacency. The boundary of a region is defined as those cells (inside the grid) that are not part of the region but are edge‐adjacent to some cell in the region.

A region which is non‐holed is called a valley if every cell inside the region has a height strictly less than every cell on its boundary. (When a boundary cell lies outside the grid, its height is considered \(\infty\).)

Bessie’s goal is to compute the sum of the sizes (the number of cells) of all valleys. Note that every connected subset (by edges) of grid cells (that does not have a hole) is considered a region and if it satisfies the valley condition then its size contributes to the answer.

Examples:

Region example:
oo.
ooo
..o
Not a region (the middle and bottom-right cells are not edge-connected):
oo.
oo.
..o
Non-holed region:
ooo
o..
o..
Holed region (a donut):
ooo
o.o
ooo
Another non-holed region (the middle cell and bottom-right cell are connected via a diagonal):
ooo
o.o
oo.

inputFormat

The first line contains an integer \(N\) representing the number of rows and columns. Then follow \(N\) lines, each containing \(N\) integers separated by spaces, representing the heights of the grid cells.

It is guaranteed that \(N\) will be small (e.g. \(N\leq 4\)) so that a brute‐force solution is feasible.

outputFormat

Output a single integer, the sum of the sizes of all valleys in the grid.

sample

1
5

1