Counting Submatrices with Minimum Green Value Equal to 100

A farmer, Farmer John, owns a huge square pasture that is divided into an N × N grid of square cells (where 1 ≤ N ≤ 500). Each cell at row i and column j has an integer green value G(i, j) (with 1 ≤ G(i, j) ≤ 200). Because of variations in the soil, some patches of grass are greener than others.

Farmer John wants to take a photograph of a submatrix of his pasture with a particular property: the minimum green value inside the submatrix must be exactly 100. In other words, every cell in the submatrix must have G(i, j) ≥ 100 and at least one cell must have G(i, j) = 100.

A key observation is that the number of valid submatrices satisfying the condition can be computed as:

[ \text{Answer} = \text{Count}{\ge100} - \text{Count}{\ge101} ]

where:

• Count≥100 is the number of submatrices whose every cell has a green value at least 100, and
• Count≥101 is the number of submatrices whose every cell has a green value at least 101.

You are given the grid, and your task is to compute and output the number of submatrices with a minimum green value exactly equal to 100.

Note: The total number of submatrices can be very large (up to about \(\frac{N^2(N+1)^2}{4}\)), so you might need to use 64-bit integers.

inputFormat

The first line of input contains an integer N (1 ≤ N ≤ 500), the size of the grid. Each of the next N lines contains N space-separated integers representing the green values G(i, j) of the grid.

outputFormat

Output a single integer: the number of submatrices whose minimum green value is exactly 100.

sample

1
100

1