#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
vector<array<int,2>> get_opt(vector<int> a)
{
int n=a.size();
vector<array<int,2>> v;
stack<int> s;
for(int i=0;i<n;i++)
{
while(!s.empty()&&a[s.top()]<a[i]) s.pop();
if(!s.empty()&&s.top()+2<=i) v.push_back({s.top(),i});
s.push(i);
}
while(!s.empty()) s.pop();
for(int i=n-1;i>=0;i--)
{
while(!s.empty()&&a[s.top()]<a[i]) s.pop();
if(!s.empty()&&i+2<=s.top()&&a[s.top()]!=a[i]) v.push_back({i,s.top()});
s.push(i);
}
return v;
}
const int N=2500;
int tree[N];
void upd(int p,int d)
{
for(;p<N;p=(p|(p+1))) tree[p]+=d;
}
int sum(int p)
{
int s=0;
for(;p>=0;p=(p&(p+1))-1) s+=tree[p];
return s;
}
int sum(int l,int r)
{
return (sum(r)-sum(l-1));
}
ll count_rectangles(vector<vector<int>> a)
{
int n=a.size();
int m=a[0].size();
vector<array<int,3>> events[n][m]; //c,t,r
vector one(n,vector(n,array<int,2>{-1,0}));
for(int j=m-1;j>=0;j--)
{
vector<int> tmp(n);
for(int i=0;i<n;i++) tmp[i]=a[i][j];
auto opt=get_opt(tmp);
for(auto [l,r]:opt)
{
if(one[l][r][0]==j+1) one[l][r][0]=j;
else one[l][r]={j,j};
events[l+1][j].push_back({one[l][r][1]+1,1,r-1});
}
}
vector two(m,vector(m,array<int,2>{-1,0}));
for(int i=n-1;i>=0;i--)
{
vector<int> tmp(m);
for(int j=0;j<m;j++) tmp[j]=a[i][j];
auto opt=get_opt(tmp);
for(auto [l,r]:opt)
{
if(two[l][r][0]==i+1) two[l][r][0]=i;
else two[l][r]={i,i};
events[i][l+1].push_back({r,0,two[l][r][1]});
}
}
ll res=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
auto &e=events[i][j];
sort(e.begin(),e.end());
for(auto [c,t,r]:e)
{
if(t==0) upd(r,1);
else res+=sum(r,n-1);
}
for(auto [c,t,r]:e) if(t==0) upd(r,-1);
}
}
return res;
}
