#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
using ll = long long;
const int N = 2509;
set < int > g[N][N];
vector < int > all[N][N];
int n, m, lft[N], rgt[N];
map < int , int > f[N];
ll count_rectangles(vector < vector < int > > a) {
n = (int)a.size(), m = (int)a[0].size();
for (int i = 0; i < n; i++) {
vector < int > v;
for (int j = 0; j < m; j++) {
while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
if (v.empty()) lft[j] = -1; else lft[j] = v.back();
v.push_back(j);
}
v.clear();
for (int j = m - 1; j >= 0; j--) {
while (!v.empty() && a[i][v.back()] <= a[i][j]) v.pop_back();
if (v.empty()) rgt[j] = -1; else rgt[j] = v.back();
v.push_back(j);
}
for (int j = 0; j < m; j++) if (lft[j] >= 0 && rgt[j] >= 0) {
all[lft[j] + 1][rgt[j] - 1].push_back(i);
}
}
for (int j = 0; j < m; j++) {
vector < int > v;
for (int i = 0; i < n; i++) {
while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back();
if (v.empty()) lft[i] = -1; else lft[i] = v.back();
v.push_back(i);
}
v.clear();
for (int i = n - 1; i >= 0; i--) {
while (!v.empty() && a[v.back()][j] <= a[i][j]) v.pop_back();
if (v.empty()) rgt[i] = -1; else rgt[i] = v.back();
v.push_back(i);
}
for (int i = 0; i < n; i++) if (lft[i] >= 0 && rgt[i] >= 0) {
int lg = lft[i] + 1, rg = rgt[i] - 1;
g[j][lg].insert(rg);
}
}
for (int j = m - 1; j >= 0; j--) {
for (int il = 0; il < n; il++) {
for (int ir : g[j][il]) {
int x = il * n + ir;
if (g[j + 1][il].find(ir) == g[j + 1][il].end()) f[j][x] = j;
else f[j][x] = f[j + 1][x];
}
}
}
ll res = 0;
for (int jl = 0; jl < m; jl++) {
for (int jr = jl; jr < m; jr++) if (!all[jl][jr].empty()) {
int p = 0;
sort(all[jl][jr].begin(), all[jl][jr].end());
while (p < (int)all[jl][jr].size()) {
int l = p;
while (l + 1 < (int)all[jl][jr].size() && all[jl][jr][l + 1] - all[jl][jr][l] <= 1) l++;
int il = all[jl][jr][p], ir = all[jl][jr][l];
for (int i1 = il; i1 <= ir; i1++) {
for (int i2 : g[jl][i1]) {
if (i2 > ir) break;
if (f[jl][i1 * n + i2] >= jr) res++;
}
}
p = l + 1;
}
}
}
return res;
}
/*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];
}
cout << count_rectangles(a);
}*/
