Farmer John's pasture can be thought of as a
NxN grid (
\(1<=N<=500\)) of square cells with grass (like a large Chess board). Due to the variability of the soil, the grass in some cells is greener than in others. Each cell
(i,j) is described by an integer - the greenness level
G(i,j), in the interval
\ (1…200\).
Farmer John wants to take a photo of a rectangular sub-grid of his pasture. He wants the minimum of G in his photo to be sharp 100. Help him count how many different pictures he can take. The subgrid can range in size from the entire pasture to one cell. There are \(N^2(N+1)^2/4\) different sublattices, use a 64-bit integer (like < code>long long in C++).
Input
The first line contains
N. Each of the following
N lines contains
N integers and together they describe the magnitudes
G(i,j) ;for pasture
NхN .
Imprint
Output the number of different photographs that Farmer John can take, i.e. the number of rectangular sublattices in which the minimum level of "greenness" exactly
100.
Note that the answer requires a 64-bit integer variable of type long long in C++.
Examples
| # |
Input |
Output |
| 1 |
3
57 120 87
200 100 150
2 141 135
| 8 |