#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;
const int N = 2510;
int a[N][N], L[N], R[N], f[N][N], g[N][N];
int n, m;
vector<tuple<int, int, int> > row[N], col[N], query[N];
stack<int> S;
int bit[N];
void up (int pos, int val) {
for(pos; pos; pos -= pos & -pos) {
S.push(pos);
bit[pos] += val;
}
}
int get(int pos) {
int ret = 0;
for(pos; pos <= n; pos += pos & -pos) ret += bit[pos];
return ret;
}
void rollback () {
while (!S.empty()) bit[S.top()] = 0, S.pop();
}
long long count_rectangles (vector<vector<int> > _a) {
n = _a.size(), m = _a[0].size();
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) a[i][j] = _a[i][j];
for(int i = 1; i < n - 1; i++) {
stack<int> st;
for(int j = 0; j < m; j++) {
while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
L[j] = st.empty() ? 0 : st.top() + 1;
st.push(j);
}
while (!st.empty()) st.pop();
for(int j = m - 1; j >= 0; j--) {
while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
R[j] = st.empty() ? m : st.top() - 1;
st.push(j);
}
for(int j = 0; j < m; j++) if (L[j] > 0 && R[j] < m - 1) row[i].emplace_back(L[j], R[j], 0);
sort(all(row[i]));
row[i].resize(unique(all(row[i])) - row[i].begin());
}
for(int i = 0; i < n; i++) row[i].emplace_back(1e9, 1e9, 1e9);
for(int j = 1; j < m - 1; j++) {
stack<int> st;
for(int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
L[i] = st.empty() ? 0 : st.top() + 1;
st.push(i);
}
while (!st.empty()) st.pop();
for(int i = n - 1; i >= 0; i--) {
while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
R[i] = st.empty() ? n : st.top() - 1;
st.push(i);
}
for(int i = 0; i < n; i++) if (L[i] > 0 && R[i] < n - 1) col[j].emplace_back(L[i], R[i], 0);
sort(all(col[j]));
col[j].resize(unique(all(col[j])) - col[j].begin());
}
for(int j = 0; j < m; j++) col[j].emplace_back(1e9, 1e9, 1e9);
for(int j = m - 2; j >= 1; j--) {
// cout << j << endl;
for(auto &[l, r, f] : col[j]) if (l != 1e9) {
auto &[_l, _r, _f] = *lower_bound(all(col[j + 1]), make_tuple(l, r, f));
if (l == _l && r == _r) f = _f;
else f = j;
// cout << l << " " << r << " " << f << " " << j << endl;
query[l].emplace_back(j, f, r);
}
}
long long ans = 0;
for(int i = n - 2; i >= 1; i--) {
int k = 0;
sort(all(query[i]));
for(auto &[l, r, f] : row[i]) {
auto &[_l, _r, _f] = *lower_bound(all(row[i + 1]), make_tuple(l, r, f));
if (l == _l && r == _r) f = _f;
else f = i;
}
int pre = 0;
for(auto &[left, right, down] : query[i]) {
if (pre != left) rollback();
while (k < row[i].size()) {
auto &[l, r, f] = row[i][k];
if (l < left) {
rollback();
k++;
continue;
}
if (l > left) break;
if (r > right) break;
pre = l;
// cout << l << " " << r << " " << f << endl;
up(f, 1);
k++;
}
if (pre != left) rollback();
ans += get(down);
// cout << get(down) << " " << i << " " << left << " " << right << endl;
}
rollback();
}
// cout << ans;
return ans;
}
// int32_t main() {
// #define task ""
// cin.tie(0) -> sync_with_stdio(0);
// if (fopen("task.inp", "r")) {
// freopen("task.inp", "r", stdin);
// freopen("task.out", "w", stdout);
// }
// if (fopen(task".inp", "r")) {
// freopen (task".inp", "r", stdin);
// freopen (task".out", "w", stdout);
// }
// int n, m; cin >> n >> m;
// vector<vector<int> > _tmp;
// for(int i = 0; i < n; i++) {
// vector<int> tmp;
// for(int j = 0; j < m; j++) {
// int x; cin >> x;
// tmp.push_back(x);
// }
// _tmp.push_back(tmp);
// }
// count_rectangles(_tmp);
// }
