#include "rect.h"
#include <bits/stdc++.h>

using namespace std;

#define pii pair<int,int>
#define F first
#define S second
#define sz(s) ((int)s.size())
#define pb push_back

const int MAX=2510;

int n,m;
map<pii,int> mp[MAX];
vector<int> f[MAX][MAX],d[MAX][MAX];
int cnt[MAX],last[MAX];
int g[MAX][MAX];
int t[MAX][MAX];

void add(int x,int y,int del){
	for(int i=x;i<=m;i=(i|(i+1))){
		for(int j=y;j<n;j=(j|(j+1))){
			t[i][j]+=del;
		}
	}
}

int get(int x,int y){
	int res=0;
	for(int i=x;i>=1;i=(i&(i+1))-1){
		for(int j=y;j>=0;j=(j&(j+1))-1){
			res+=t[i][j];
		}
	}
	return res;
}

int get(int lx,int rx,int ly,int ry){
	int res=get(rx,ry);
	if(lx-1>=1&&ly-1>=0)res+=get(lx-1,ly-1);
	if(lx-1>=1){
		res-=get(lx-1,ry);
	}
	if(ly-1>=0){
		res-=get(rx,ly-1);
	}
	return res;
}

long long count_rectangles(vector<vector<int>> a){
	n=sz(a),m=sz(a[0]);
	for(int i=0;i<n;i++){
		stack<int> st;
		for(int j=0;j<m;j++){
			while(!st.empty()&&a[i][st.top()]<=a[i][j]){
				int l=st.top()+1,r=j-1;
				if(l<=r){
					mp[i][{l,r}]=1;
					// cout<<"!i<<" "<<l<<" "<<j-1<<"\n";
					d[i][l].pb(j-1);
				}
				st.pop();
			}
			if(!st.empty()){
				int l=st.top()+1;
				if(l<=j-1){
					mp[i][{l,j-1}]=1;
					d[i][l].pb(j-1);
				}
			}
			st.push(j);
		}
	}
	for(int j=0;j<m;j++){
		stack<int> st;
		for(int i=0;i<n;i++){
			while(!st.empty()&&a[st.top()][j]<=a[i][j]){
				int l=st.top()+1,r=i-1;
				if(l<=r){
					f[l][j].pb(r);
				}
				st.pop();
			}
			if(!st.empty()){
				int l=st.top()+1;
				if(l<=i-1){
					f[l][j].pb(i-1);
				}
			}
			st.push(i);
		}
	}
	long long ans=0;
	for(int i=n-2;i>0;i--){
		memset(last,-1,sizeof(last));
		memset(cnt,0,sizeof(cnt));
		for(int j=m-2;j>0;j--){
			// cout<<"? "<<i<<" "<<j<<"\n";
			for(auto r:f[i][j]){
				if(last[r]==j+1){
					cnt[r]++;
				}
				else cnt[r]=1;
				last[r]=j;
				// cout<<cnt[r]<<" "<<i<<" "<<r<<"\n";
				add(cnt[r],r,1);
			}
			for(auto r:d[i][j]){
				if(mp[i+1].count({j,r}))g[j][r]++;
				else g[j][r]=1;
				// if(i==4&&j==2){
				// 	cout<<r-j+1<<" "<<m<<" "<<i<<" "<<i+g[j][r]-1<<" "<<cnt[4]<<"\n";
				// 	cout<<i<<" "<<j<<" "<<r<<" "<<g[j][r]<<" "<<get(r-j+1,m,i,i+g[j][r]-1)<<"\n";
				// }
				ans+=get(r-j+1,m,i,i+g[j][r]-1);
			}
			for(auto r:f[i][j]){
				add(cnt[r],r,-1);
			}
		}
	}
	return ans;
}