//by szh
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back
#define debug(x) cerr<<#x<<"="<<x<<endl
#define pq priority_queue
#define inf 0x3f
#define rep(i,a,b) for (int i=a;i<(b);i++)
#define MP make_pair
#define SZ(x) (int(x.size()))
#define ll long long
#define mod 1000000007
#define ALL(x) x.begin(),x.end()
void inc(int &a,int b) {a=(a+b)%mod;}
void dec(int &a,int b) {a=(a-b+mod)%mod;}
int lowbit(int x) {return x&(-x);}
ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;}
#include "rect.h"
int N,M;
const int maxn = 2555;
int grid[maxn][maxn];
vector <pair<pii,int> > row1[maxn];
vector <pii> row[maxn][maxn];
vector <pii> hi[maxn];
int tree[maxn][maxn];
stack <int> q;
int lft[maxn][maxn],rit[maxn][maxn];
void update(pii tmp,int val) {
int pos = tmp.se;
while (pos<maxn) {
tree[tmp.fi][pos] += val;
pos += lowbit(pos);
}
return;
}
int query(int id,int pos) {
int ret = 0;
while (pos) {
ret += tree[id][pos];
pos -= lowbit(pos);
}
return ret;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
N = SZ(a),M=SZ(a[0]);
rep(i,0,N) rep(j,0,M) grid[i][j] = a[i][j];
memset(lft,-1,sizeof(lft));memset(rit,-1,sizeof(rit));
rep(i,1,N-1) {
while (!q.empty()) q.pop();
rep(j,0,M) {
while (!q.empty() and a[i][q.top()]<a[i][j]) q.pop();
if (!q.empty() and q.top()!=j-1) hi[i].pb({q.top(),j}),lft[i][j] = q.top();
q.push(j);
}
while (!q.empty()) q.pop();
for (int j = M-1;j>=0;j--) {
while (!q.empty() and a[i][q.top()]<a[i][j]) q.pop();
if (!q.empty() and q.top()!=j+1) hi[i].pb({j,q.top()}),rit[i][j] = q.top();
q.push(j);
}
}
rep(i,1,N-1) {
for (auto it:hi[i]) {
if (lft[i][it.se]!=it.fi and rit[i][it.fi]!=it.se) continue;
if (lft[i][it.se]==it.fi) lft[i][it.se]=-1;
if (rit[i][it.fi]==it.se) rit[i][it.fi] = -1;
int cur = i+1;
while (cur<N-1 and (lft[cur][it.se]==it.fi or rit[cur][it.fi]==it.se)) {
if (lft[cur][it.se]==it.fi) lft[cur][it.se]=-1;
if (rit[cur][it.fi]==it.se) rit[cur][it.fi] = -1;
cur++;
}
rep(j,i,cur) row1[j].pb({{it.fi+1,it.se-1},cur-1});
}
while (!hi[i].empty()) hi[i].pop_back();
sort(ALL(row1[i]));
}
memset(lft,-1,sizeof(lft));memset(rit,-1,sizeof(rit));
rep(i,1,M-1) {
while (!q.empty()) q.pop();
rep(j,0,N) {
while (!q.empty() and a[q.top()][i]<a[j][i]) q.pop();
if (!q.empty() and q.top()!=j-1) hi[i].pb({q.top(),j}),lft[j][i] = q.top();
q.push(j);
}
while (!q.empty()) q.pop();
for (int j = N-1;j>=0;j--) {
while (!q.empty() and a[q.top()][i]<a[j][i]) q.pop();
if (!q.empty() and q.top()!=j+1) hi[i].pb({j,q.top()}),rit[j][i] = q.top();
q.push(j);
}
}
rep(i,1,M-1) {
for (auto it:hi[i]) {
if (lft[it.se][i]!=it.fi and rit[it.fi][i]!=it.se) continue;
int cur = i+1;
if (lft[it.se][i]==it.fi) lft[it.se][i] = -1;
if (rit[it.fi][i]==it.se) rit[it.fi][i] = -1;
while (cur<M-1 and (lft[it.se][cur]==it.fi or rit[it.fi][cur] == it.se)) {
if (lft[it.se][cur]==it.fi) lft[it.se][cur] = -1;
if (rit[it.fi][cur]==it.se) rit[it.fi][cur] = -1;
cur++;
}
rep(j,i,cur) row[(it).fi+1][i].pb({j,(it).se-1});
}
}
ll ans = 0;
rep(i,1,N-1) {
int cur = 1;
vector <pii> tmp;
for (auto it:row1[i]) {
while (cur<=it.fi.fi) {
for (auto itt:row[i][cur]) update(itt,1),tmp.pb(itt);
cur++;
}
ans += query(it.fi.se,it.se);
// cout<<it.fi.fi<<" "<<it.fi.se<<" "<<i<<" "<<it.se<<" "<<ans<<endl;
}
while (!tmp.empty()) update(tmp.back(),-1),tmp.pop_back();
}
return ans;
}
