题目描述

金融分析机构正在研究一张 $N \times N$ 的市场波动数据表（$1 \le N \le 500$）。表中的每个单元格 $(i, j)$ 记录了一个波动指数 $W(i, j)$，该指数的范围是 $[1, 200]$ 之间的整数。

分析师需要从这张大表中截取出一块子矩阵区域进行重点分析。一个合格的子矩阵区域必须满足：子矩阵区域内所有波动指数的最小值恰好等于 $100$。

这意味着，这个区域内所有单元格的波动指数都 $\ge 100$，并且至少有一个单元格的波动指数恰好等于 $100$。

请你计算，分析师可以从中截取出多少个不同的、满足上述条件的子矩阵区域。子矩阵最小可以仅为一个单元格，最大可以为整个数据表。

输入格式

输入的第一行包含一个整数 $N$，表示数据表的尺寸。

接下来的 $N$ 行，每行包含 $N$ 个整数，表示 $N \times N$ 数据表中的波动指数 $W(i, j)$。

输出格式

输出一个整数，表示满足条件的子矩阵区域的总数量。

样例 #1

输入

3
57 120 87
200 100 150
2 141 135

输出

8

样例 #2

输入

6
51 184 167 180 140 100
57 100 151 72 2 195
41 179 109 88 72 40
56 196 87 27 100 98
25 92 89 155 68 12
187 118 100 32 97 21

输出

20

样例 #3

输入

8
100 120 100 120 100 120 100 120
120 110 120 110 120 110 120 110
100 120 100 120 100 120 100 120
120 110 120 99 120 110 120 110
100 120 100 120 99 120 100 120
120 110 120 110 120 110 120 110
100 120 100 120 100 120 100 120
120 110 120 110 120 110 120 110

输出

519

样例说明

样例 1 说明

数据表为 $3 \times 3$。我们寻找最小波动指数恰好为 $100$ 的子矩阵。

表中，只有 $(2, 2)$ 单元格的波动指数恰好为 $100$。

以 $(2, 2)$ 为关键单元格（即最小值所在单元格）的子矩阵有：

• 仅包含 $(2, 2)$ 自身：$[(2, 2)]$，最小值为 $100$。
• 包含 $(1, 2), (2, 2)$：$(120, 100)$，最小值为 $100$。
• 包含 $(2, 1), (2, 2)$：$(200, 100)$，最小值为 $100$。
• 包含 $(2, 2), (2, 3)$：$(100, 150)$，最小值为 $100$。
• 包含 $(2, 2), (3, 2)$：$(100, 141)$，最小值为 $100$。
• 包含 $(1, 2), (2, 2), (3, 2)$ 所在的整列，最小值为 $\min(120, 100, 141) = 100$。
• 包含 $(2, 1), (2, 2), (2, 3)$ 所在的整行，最小值为 $\min(200, 100, 150) = 100$。
• 包含 $(2, 2), (2, 3), (3, 2), (3, 3)$ 所在的行列，最小值为 $\min(100, 150, 141, 135) = 100$。

总共有 $8$ 个满足条件的子矩阵。

数据范围

对于 $100\%$ 的数据，满足 $1 \le N \le 500$，$1 \le W(i, j) \le 200$。

测试点编号	$N$
$1 \sim 5$	$\le 200$
$6 \sim 10$	$\le 500$