// [+] https://oj.uz/submission/286084
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2505;
int lh[N], rh[N], lw[N], rw[N], a[N][N];
pair<int, int> range[N][N];
enum class EventType {
add,
get
};
struct Event {
EventType type;
int r, c;
Event() = default;
Event(EventType type, int r, int c):
type(type), r(r), c(c) {}
bool operator < (const Event &other) const {
return tie(r, type) < tie(other.r, other.type);
}
};
vector<Event> events[N][N];
struct FenwickTree {
int BIT[N], n = N - 1, all = 0;
FenwickTree() = default;
FenwickTree(int n): n(n) {}
void update(int x, int w) {
for (; x <= n; x += x & -x)
BIT[x] += w;
all += w;
}
int pref(int x) {
int ans = 0;
for (; x > 0; x -= x & -x)
ans += BIT[x];
return ans;
}
int suff(int x) {
return all - pref(x - 1);
}
} cnt;
ll count_rectangles(vector<vector<int>> b) {
int m = b.size(), n = b[0].size();
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
a[i][j] = b[i - 1][j - 1];
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j++)
range[i][j] = {-1, -1};
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
lw[j] = j - 1;
while (lw[j] > 0 && a[i][j] >= a[i][lw[j]])
lw[j] = lw[lw[j]];
}
for (int j = n; j > 0; j--) {
rw[j] = j + 1;
while (rw[j] <= n && a[i][j] >= a[i][rw[j]])
rw[j] = rw[rw[j]];
}
for (int j = 1; j <= n; j++) {
int l = lw[j] + 1, r = rw[j] - 1;
if (1 < l && l <= r && r < n && range[l][r].second != i) {
if (range[l][r].second == i - 1)
range[l][r].second++;
else range[l][r] = {i, i};
int len = range[l][r].second - range[l][r].first + 1;
events[i][r].emplace_back(EventType::get, len, r - l + 1);
}
}
}
for (int i = 1; i <= m; i++)
for (int j = i; j <= m; j++)
range[i][j] = {-1, -1};
for (int j = 1; j <= n; j++) {
for (int i = 1; i <= m; i++) {
lh[i] = i - 1;
while (lh[i] > 0 && a[i][j] >= a[lh[i]][j])
lh[i] = lh[lh[i]];
}
for (int i = m; i > 0; i--) {
rh[i] = i + 1;
while (rh[i] <= m && a[i][j] >= a[rh[i]][j])
rh[i] = rh[rh[i]];
}
for (int i = 1; i <= m; i++) {
int l = lh[i] + 1, r = rh[i] - 1;
if (1 < l && l <= r && r < m && range[l][r].second != j) {
if (range[l][r].second == j - 1)
range[l][r].second++;
else range[l][r] = {j, j};
int len = range[l][r].second - range[l][r].first + 1;
events[r][j].emplace_back(EventType::add, r - l + 1, len);
}
}
}
ll ans = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
auto &events = ::events[i][j];
sort(events.begin(), events.end());
for (const auto &event: events) {
if (event.type == EventType::add) {
cnt.update(event.c, +1);
} else {
ans += cnt.suff(event.c);
}
}
for (const auto &event: events)
if (event.type == EventType::add)
cnt.update(event.c, -1);
}
}
return ans;
}
#ifdef LOCAL
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
}
}
long long result = count_rectangles(a);
cout << result;
return 0;
}
#endif
