#include <vector>
#include<bits/stdc++.h>
using namespace std;
using ll = int;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 2510;
const ll MAXK = 13;
vector <pll> row[MAXN][MAXN];
vector <pair <ll,pll> > col[MAXN][MAXN];
pll bound[MAXN][MAXN];
vector <ll> down[MAXN][MAXN];
ll sp[MAXK][MAXN];
vector <ll> b;
ll highest(ll x,ll y){
if (b[y]>b[x])return y;
return x;
}
ll query(ll l,ll r){
ll sz = __lg(r-l+1);
return highest(sp[sz][l],sp[sz][r-MASK(sz)+1]);
}
void solve(ll l,ll r,vector <pll> &ans){
if (l > r)return;
ll mid = query(l,r);
solve(l,mid-1,ans);
solve(mid+1,r,ans);
ans[mid] = MP(l,r);
}
vector <pll> build(){
ll n = sz(b);
for (ll i = 0;i < n;i ++){
sp[0][i] = i;
}
for (ll j = 1;j < MAXK;j ++){
for (ll i = 0;i + MASK(j) - 1 < n;i ++){
sp[j][i] = highest(sp[j-1][i],sp[j-1][i+MASK(j-1)]);
}
}
vector <pll> res(n);
solve(0,n-1,res);
for (ll i = 0;i < n;i ++){
if (res[i].fi == 0 || res[i].se == n-1 || b[res[i].fi-1] <= b[i] || b[res[i].se+1] <= b[i])res[i] = MP(-1,-1);
}
return res;
}
long long count_rectangles(std::vector<std::vector<int> > a){
ll n = sz(a);
ll m = sz(a[0]);
// cout<<n<<' '<<m<<endl;
for (ll i = 0;i < n; i ++){
b = a[i];
vector <pll> tmp = build();
for (ll j = 0;j < m;j ++){
bound[i][j] = tmp[j];
if (bound[i][j].fi != -1)row[bound[i][j].fi][bound[i][j].se].push_back(MP(i,0));
}
}
for (ll i = 0;i < m;i ++){
for (ll j = i;j < m;j ++){
for (ll k = sz(row[i][j])-1;k>=0;k--){
if (k == sz(row[i][j])-1 || row[i][j][k].fi + 1 < row[i][j][k+1].fi)row[i][j][k].se = row[i][j][k].fi ;
else row[i][j][k].se = row[i][j][k+1].se;
// if (i==j&&j==1)cout<<row[i][j][k].fi<<' '<<row[i][j][k].se<<endl;
}
}
}
for (ll j = 0;j < m;j ++){
b.resize(n);
for (ll i = 0;i < n;i ++){
b[i] = a[i][j];
}
vector <pll> tmp = build();
for (auto x:tmp){
if (x.fi==-1)continue;
col[x.fi][x.se].push_back(MP(j,MP(0,0)));
down[x.fi][j].push_back(x.se);
}
}
for (ll i = 0;i < n;i ++){
for (ll j = i;j < n;j ++){
for (ll k = sz(col[i][j])-1;k>=0;k--){
if (k == sz(col[i][j])-1 || col[i][j][k].fi + 1 < col[i][j][k+1].fi)col[i][j][k].se.se = col[i][j][k].fi;
else col[i][j][k].se.se = col[i][j][k+1].se.se;
}
for (ll k = 0;k < sz(col[i][j]);k ++){
if (k == 0 || col[i][j][k].fi - 1 > col[i][j][k-1].fi)col[i][j][k].se.fi = col[i][j][k].fi;
else col[i][j][k].se.fi = col[i][j][k-1].se.fi;
}
}
}
ll res = 0;
for (ll i = 0;i < n;i ++){
for (ll j = 0;j < m;j ++){
if (bound[i][j].fi==-1)continue;
ll l = bound[i][j].fi,r = bound[i][j].se;
ll max1 = (*lower_bound(row[l][r].begin(),row[l][r].end(),MP(i,-1))).se;
// cout<<i<<' '<<j<<' '<<l<<' '<<r<<' '<<max1<<endl;
for (auto x:down[i][j]){
pll tmp = (*lower_bound(col[i][x].begin(),col[i][x].end(),MP(j,MP(-1,-1)))).se;
// cout<<x<<' '<<tmp.fi<<' '<<tmp.se<<endl;
if (tmp.fi <= l && tmp.se >= r && x <= max1){
// cout<<i<<' '<<l<<' '<<x<<' '<<r<<endl;
res++;
}
}
}
}
return res;
}
