#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#include <set>
using namespace std;
struct Node {
int sum = 0, l = -1, r = -1;
};
struct SparseSeg{
vector<Node> cache;
void insert(int l, int r, int i, int v){
//if (r <= v || v <= l) return;
if (l + 1 == r) {
++cache[i].sum;
return;
}
int m = l + (r-l)/2;
if (v >= m) {
if (cache[i].r == -1) {
cache[i].r = cache.size();
cache.push_back({});
}
insert(m, r, cache[i].r, v);
}
else {
if (cache[i].l == -1) {
cache[i].l = cache.size();
cache.push_back({});
}
insert(l, m, cache[i].l, v);
}
++cache[i].sum;
}
int postfixsum (int l, int r, int i, int ii){
if (l + 1 == r) return cache[i].sum;
int m = l + (r-l)/2;
if (ii < m) {
int ret = 0;
if (cache[i].l != -1) ret += postfixsum(l, m, cache[i].l, ii);
if (cache[i].r != -1) ret += cache[cache[i].r].sum;
return ret;
}
else {
if (cache[i].r != -1) return postfixsum(m, r, cache[i].r, ii);
return 0;
}
}
};
#define MAXN 2500
int n, m;
array<array<vector<int16_t>, MAXN>, MAXN> hors, verts;
vector<vector<signed>> aG;
array<array<vector<pair<int16_t, int16_t>>, MAXN>, MAXN> hpossibs, vpossibs;
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);
for (int j = m - 2; j >= 0; --j) {
for (int i = 0; i < n; ++i) {
sort(verts[i][j].begin(), verts[i][j].end());
auto itt = vpossibs[i][j+1].begin();
auto cs = verts[i][j].begin();
while (itt != vpossibs[i][j+1].end() && cs != verts[i][j].end()){
if ((*itt).second == *cs) vpossibs[i][j].emplace_back((*itt++).first + 1, *cs++);
else if ((*itt).second < *cs) itt++;
else vpossibs[i][j].emplace_back(1, *cs++);;
}
while (cs != verts[i][j].end()) vpossibs[i][j].emplace_back(1, *cs++);
}
}
for (int i = n - 2; i >= 0; --i) {
for (int j = 0; j < m; ++j) {
sort(hors[i][j].begin(), hors[i][j].end());
auto itt = hpossibs[i + 1][j].begin();
auto cs = hors[i][j].begin();
while (itt != hpossibs[i + 1][j].end() && cs != hors[i][j].end()){
if ((*itt).first == *cs) hpossibs[i][j].emplace_back(*cs++, (*itt++).second + 1);
else if ((*itt).first < *cs) itt++;
else hpossibs[i][j].emplace_back(*cs++, 1);
}
while (cs != hors[i][j].end()) hpossibs[i][j].emplace_back(*cs++, 1);
}
}
int ans = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
//SparseSeg seg;
//seg.cache.push_back({});
multiset<int> hlimits;
sort(vpossibs[i][j].begin(), vpossibs[i][j].end());
auto hor = hpossibs[i][j].begin();
auto ver = vpossibs[i][j].begin();
while (hor != hpossibs[i][j].end() && ver != vpossibs[i][j].end()){
if ((*hor).first <= (*ver).first) hlimits.insert((*hor++).second);
else ans += distance(hlimits.lower_bound((*ver++).second), hlimits.end());
}
while (ver != vpossibs[i][j].end()) ans += distance(hlimits.lower_bound((*ver++).second), hlimits.end());
}
}
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;
}*/
