#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=2502;
int val[maxn][maxn], v[maxn], pref[maxn], suf[maxn];
ll solve(int l, int r){
if(l>r) return 0ll;
pref[l-1]=v[l-1];
suf[r+1]=v[r+1];
for(int i=l;i<=r;i++) pref[i]=max(pref[i-1],v[i]);
for(int i=r;i>=l;i--) suf[i]=max(suf[i+1],v[i]);
ll ret=0;
for(int i=l;i<=r;i++) if(pref[i]!=v[i]&&suf[i]!=v[i]) ret++;
return ret;
}
ll count_rectangles(vector<vector<int> > a){
int n=a.size(), m=a[0].size();
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
val[i+1][j+1]=a[i][j];
if(min(n,m)<3) return 0ll;
for(int i=1;i<=m;i++) v[i]=val[2][i];
int last=0;
ll resp=0;
for(int i=1;i<=m;i++){
if(val[2][i]>=min(val[1][i],val[3][i])){
resp+=solve(last+1,i-1);
last=i;
}
}
resp+=solve(last+1,m);
return resp;
}
