#include <bits/stdc++.h>
#define ll long long
#define forn(j, i, n) for(int i = j; i <= n; ++i)
#define FOR(j, i, n) for(int i = j; i < n; ++i)
#define nfor(j, i, n) for(int i = n; i >= j; --i)
#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
#define IOS ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
const int maxn=2e5+10;
int n, m, fen[maxn];
void updfen(int r, int val)
{
for(; r <= m; r = ((r + 1) | r)) fen[r] += val;
}
int getfen(int r)
{
int ret = 0;
for(; r >= 0; r = ((r+1)&r)-1) ret += fen[r];
return ret;
}
long long count_rectangles(vector<vector<int> > A)
{
n = A.size();
m = A[0].size();
vector <vector <int> > a(n+2), L(n+2), R(n+2), up(n+2), down(n+2);
forn(0, i, n+1)
{
a[i].assign(m+2, 0);
up[i].assign(m+2, 0);
down[i].assign(m+2, 0);
L[i].assign(m+2, 0);
R[i].assign(m+2, 0);
}
forn(1, i, n)
{
forn(1, j, m) a[i][j] = A[i-1][j-1];
}
forn(1, i, n)
{
stack <int> st;
forn(1, j, m)
{
while(st.size() && a[i][st.top()] < a[i][j])
{
st.pop();
}
if(st.size())
L[i][j] = st.top();
else
L[i][j] = 0;
st.push(j);
}
while(st.size()) st.pop();
nfor(1, j, m)
{
while(st.size() && a[i][st.top()] < a[i][j])
{
st.pop();
}
if(st.size())
R[i][j] = st.top();
else
R[i][j] = m+1;
st.push(j);
}
}
forn(1, j, m)
{
stack <int> st;
forn(1, i, n)
{
while(st.size() && a[st.top()][j] < a[i][j])
{
st.pop();
}
if(st.size())
up[i][j] = st.top();
else
up[i][j] = 0;
st.push(i);
}
while(st.size()) st.pop();
nfor(1, i, n)
{
while(st.size() && a[st.top()][j] < a[i][j])
{
st.pop();
}
if(st.size())
down[i][j] = st.top();
else
down[i][j] = n+1;
st.push(i);
}
}
ll ans = 0;
vector <int> R2(m+2, 0), L2(m+2, 0);
vector <vector <int> > start;
start.assign(m+2, {});
forn(1, r1, n)
{
forn(1, c, m)
{
R2[c] = R[r1+1][c];
L2[c] = L[r1+1][c];
}
forn(r1+2, r2, n)
{
int latest_bad = m;
forn(1, c1, m)
{
fen[c1] = 0;
start[c1].clear();
}
nfor(1, c1, m)
{
if(min(R2[c1], latest_bad) >= c1+2)
ans += getfen(min(R2[c1], latest_bad));
// if(getfen(min(R2[c1], latest_bad)))
// cout << r1 << " " << r2 << " " << c1 << " " << getfen(min(R2[c1], latest_bad)) << " " << latest_bad << " " << R2[c1] << endl;
start[L2[c1]].pb(c1);
updfen(c1, 1);
for(auto i : start[c1])
{
updfen(i, -1);
}
if(up[r2][c1] < r1 || down[r1][c1] > r2) latest_bad = c1;
}
forn(1, c1, m)
{
L2[c1] = max(L2[c1], L[r2][c1]);
R2[c1] = min(R2[c1], R[r2][c1]);
}
}
}
return ans;
}
