#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;
long long count_rectangles(vector<vector<int> > A)
{
int n = A.size();
int 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;
forn(1, r1, n)
{
forn(r1 + 2, r2, n)
{
forn(1, c1, m)
{
forn(c1 + 2, c2, m)
{
int bad = 0;
forn(c1+1, j, c2-1)
{
if(down[r1][j] < r2) bad = 1;
if(up[r2][j] > r1) bad = 1;
}
forn(r1+1, i, r2-1)
{
if(R[i][c1] < c2) bad = 1;
if(L[i][c2] > c1) bad = 1;
}
if(!bad)
{
ans++;
// cout << r1 << " " << c1 << " " << r2 << " " << c2 << endl;
}
}
}
}
}
return ans;
}
