#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define F first
#define S second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = sz(a);
int m = sz(a[0]);
vector<vector<map<int,int>>> rowf(n,vector<map<int,int>>(m));
rep(i,0,n){
vector<pii> stack;
rep(j,0,m){
while(sz(stack) && stack.back().F < a[i][j]){
if(stack.back().S+1 <= j-1) {
rowf[i][stack.back().S+1][j-1]=-1;
// cout<<"push "<<(stack.back().S+1)<<" to "<<j-1<<endl;
}
stack.pop_back();
}
if(sz(stack) && stack.back().S+1 <= j-1) {
// cout<<"push "<<(stack.back().S+1)<<" to "<<j-1<<endl;
rowf[i][stack.back().S+1][j-1]=-1;
}
while(sz(stack) && stack.back().F == a[i][j]) stack.pop_back();
stack.pb({a[i][j],j});
}
}
vector<vector<map<int,int>>> colf(n,vector<map<int,int>>(m));
rep(j,0,m){
vector<pii> stack;
rep(i,0,n){
while(sz(stack) && stack.back().F < a[i][j]){
if(stack.back().S+1<=i-1) colf[stack.back().S+1][j][i-1]=-1;
stack.pop_back();
}
if(sz(stack) && stack.back().S+1<=i-1) colf[stack.back().S+1][j][i-1]=-1;
while(sz(stack) && stack.back().F == a[i][j]) stack.pop_back();
stack.pb({a[i][j],i});
}
}
rep(i,0,n)rep(j,0,m){
for(auto p : rowf[i][j]){
if(p.S == -1){
int k = i;
while(k<n && rowf[k][j].count(p.F)) k++;
rep(l,i,k) rowf[l][j][p.F]=k-1;
}
}
for(auto p : colf[i][j]){
if(p.S == -1){
int k = j;
while(k<m && colf[i][k].count(p.F)) k++;
rep(l,j,k) colf[i][l][p.F]=k-1;
}
}
}
// rep(i,0,n){
// rep(j,0,m){
// cout<<i<<' '<<j<<" rows:";
// for(pii x : rowf[i][j]) cout<<' '<<x.F<<","<<x.S;
// cout<<endl;
// cout<<i<<' '<<j<<" cols:";
// for(pii x : colf[i][j]) cout<<' '<<x.F<<","<<x.S;
// cout<<endl;
// }
// }
ll ans = 0;
rep(i,0,n){
rep(j,0,m){
for(pii l : colf[i][j])for(pii r : rowf[i][j]){
// [i, r.F], r.S tells how far we go on other
// [j, l.F], l.S tells how far we go on other
if(l.S < r.F) break;
bool good = l.S>=r.F && r.S >= l.F;
// cout<<i<<' '<<j<<" ("<<l.F<<','<<l.S<<") ("<<r.F<<','<<r.S<<") "<<good<<endl;
ans += good;
}
}
}
return ans;
}
