#include "rect.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 2500;
#define LO(x) ((x) & (-(x)))
struct BIT {
int n, tot;
int a[MAXN + 10];
void init(int _n) {
n = _n;
tot = 0;
memset(a, 0, sizeof(a));
}
void add(int i, int x) {
while(i <= n) {
a[i] += x;
i += LO(i);
}
tot += x;
}
int ask(int i) {
int res = 0;
while(i) {
res += a[i];
i -= LO(i);
}
return res;
}
int suf(int i) {
return tot - ask(i - 1);
}
} bit;
vector<pii> ver[MAXN + 10][MAXN + 10];
vector<pii> hor[MAXN + 10][MAXN + 10];
long long count_rectangles(vector<vector<int32_t>> a) {
int n = sz(a);
int m = sz(a[0]);
// collect 'sticks'
vector<pii> stk; // {index, value}
// horizontal sticks
For(i, 0, n - 1) {
stk.clear();
For(j, 0, m - 1) {
while(sz(stk) && stk.back().S < a[i][j]) stk.pop_back();
if(sz(stk) && stk.back().F + 1 <= j - 1) hor[i][j - 1].eb(i, stk.back().F + 1);
stk.eb(j, a[i][j]);
}
stk.clear();
Forr(j, m - 1, 0) {
while(sz(stk) && stk.back().S <= a[i][j]) stk.pop_back();
if(sz(stk) && stk.back().F - 1 >= j + 1) hor[i][stk.back().F - 1].eb(i, j + 1);
stk.eb(j, a[i][j]);
}
}
// vertical sticks
For(j, 0, m - 1) {
stk.clear();
For(i, 0, n - 1) {
while(sz(stk) && stk.back().S < a[i][j]) stk.pop_back();
if(sz(stk) && stk.back().F + 1 <= i - 1) ver[i - 1][j].eb(stk.back().F + 1, j);
stk.eb(i, a[i][j]);
}
stk.clear();
Forr(i, n - 1, 0) {
while(sz(stk) && stk.back().S <= a[i][j]) stk.pop_back();
if(sz(stk) && stk.back().F - 1 >= i + 1) ver[stk.back().F - 1][j].eb(i + 1, j);
stk.eb(i, a[i][j]);
}
}
// merge sticks
For(i, 1, n - 2) For(j, 1, m - 2) {
map<int, int> mp;
for(auto &p:hor[i - 1][j]) mp[p.S] = p.F;
for(auto &p:hor[i][j]) {
if(mp.count(p.S)) p.F = mp[p.S];
}
mp.clear();
for(auto &p:ver[i][j - 1]) mp[p.F] = p.S;
for(auto &p:ver[i][j]) {
if(mp.count(p.F)) p.S = mp[p.F];
}
}
// cerr << "horizontal:\n";
// For(i, 0, n - 1) For(j, 0, m - 1) for(auto &k:hor[i][j]) {
// cerr << "[" << k.F << ", " << i << "] : ";
// cerr << "[" << k.S << ", " << j << "]\n";
// }
// cerr << "vertical:\n";
// For(i, 0, n - 1) For(j, 0, m - 1) for(auto &k:ver[i][j]) {
// cerr << "[" << k.F << ", " << i << "] : ";
// cerr << "[" << k.S << ", " << j << "]\n";
// }
// count answer
int ans = 0;
bit.init(n);
For(i, 1, n - 2) For(j, 1, m - 2) {
int cnt = 0;
vector<pair<int, pii>> v;
for(auto &p:ver[i][j]) v.eb(0, p);
for(auto &p:hor[i][j]) v.eb(1, p);
sort(all(v), [&](pair<int, pii> &p1, pair<int, pii> &p2) {
if(p1.S.S != p2.S.S) return p1.S.S < p2.S.S;
if(p1.S.F != p2.S.F) return p1.S.F > p2.S.F;
return p1.F < p2.F;
});
for(auto &it:v) {
int ii, jj;
tie(ii, jj) = it.S;
ii++; jj++;
if(it.F == 0) {
bit.add(ii, 1);
} else {
cnt += bit.suf(ii);
}
}
for(auto &it:v) {
if(it.F == 0) {
bit.add(it.S.F + 1, -1);
}
}
ans += cnt;
// cerr << i << " " << j << " " << cnt << " " << sz(v) << "\n";
}
return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
6
*/
