#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <set>
using namespace std;
#define MAXN 2500
int n, m;
array<array<vector<int16_t>, MAXN>, MAXN> hors, verts;
vector<vector<signed>> aG;
void line(int i){
vector<int> records = {0};
for (int j = 1; j < m; ++j) {
bool rsame = false;
while (!records.empty() && aG[i][j] >= aG[i][records.back()]){
if (aG[i][j] == aG[i][records.back()]) rsame = true;
if (records.back() + 1 < j) hors[i][records.back() + 1].push_back(j - records.back() - 1);
records.pop_back();
}
if (!records.empty() && records.back() + 1 < j && !rsame) hors[i][records.back() + 1].push_back(j - records.back() - 1);
records.push_back(j);
}
}
void column(int j){
vector<int> records = {0};
for (int i = 1; i < n; ++i) {
bool rsame = false;
while (!records.empty() && aG[i][j] >= aG[records.back()][j]){
if (aG[i][j] == aG[records.back()][j]) rsame = true;
if (records.back() + 1 < i) verts[records.back() + 1][j].push_back(i - records.back() - 1);
records.pop_back();
}
if (!records.empty() && records.back() + 1 < i && !rsame) verts[records.back() + 1][j].push_back(i - records.back() - 1);
records.push_back(i);
}
}
long long count_rectangles(vector<vector<signed>> a){
n = a.size(); m = a[0].size(); swap(aG, a);
for (int i = 0; i < n; ++i) line(i);
for (int j = 0; j < m; ++j) column(j);
int ans = 0;
array<vector<pair<int, int>>, MAXN> lastr;
for (int j = m - 2; j >= 0; --j) {
array<vector<pair<int, int>>, MAXN> tr;
vector<pair<int, int>> down;
for (int i = n - 2; i >= 0; --i) {
sort(verts[i][j].begin(), verts[i][j].end());
auto itt = lastr[i].begin();
auto cs = verts[i][j].begin();
while (itt != lastr[i].end() && cs != verts[i][j].end()){
if ((*itt).second == *cs) tr[i].emplace_back((*itt++).first + 1, *cs++);
else if ((*itt).second < *cs) itt++;
else tr[i].emplace_back(1, *cs++);;
}
while (cs != verts[i][j].end()) tr[i].emplace_back(1, *cs++);
vector<pair<int, int>> here;
sort(hors[i][j].begin(), hors[i][j].end());
itt = down.begin();
cs = hors[i][j].begin();
while (itt != down.end() && cs != hors[i][j].end()){
if ((*itt).first == *cs) here.emplace_back(*cs++, (*itt++).second + 1);
else if ((*itt).first < *cs) itt++;
else here.emplace_back(*cs++, 1);
}
while (cs != hors[i][j].end()) here.emplace_back(*cs++, 1);
multiset<int> hlimits;
vector<pair<int, int>> vcopy = tr[i];
sort(vcopy.begin(), vcopy.end());
auto hor = here.begin();
auto ver = vcopy.begin();
while (hor != here.end() && ver != vcopy.end()){
if ((*hor).first <= (*ver).first) hlimits.insert((*hor++).second);
else ans += distance(hlimits.lower_bound((*ver++).second), hlimits.end());
}
while (ver != vcopy.end()) ans += distance(hlimits.lower_bound((*ver++).second), hlimits.end());
swap(down, here);
}
swap(lastr, tr);
}
return ans;
}
/*
signed main(){
cerr << count_rectangles({{10, 9, 8, 9, 10},
{9 , 8, 7, 8, 9 },
{8 , 7, 6, 7, 8 },
{7 , 6, 5, 6, 7 },
{8 , 7, 6, 7, 8 },
{9 , 8, 7, 8, 9 },
{10, 9, 8, 9, 10}}) << "\n";
return 0;
}*/
