#pragma GCC optimize("O2")
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
int const N=2501,LG=12;
struct spmx //sparse table for max
{
int sp[N][LG]={};
spmx(vector<int>vals)
{
int n=vals.size();
for (int i=0;i<n;i++)
sp[i][0]=vals[i];
for (int j=1;(1<<j)<=n;j++)
for (int i=0;i+(1<<j)-1<n;i++)
sp[i][j]=max(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
inline int get(int l,int r)
{
if (l>r)
return 1e9;
int lg=log2(r-l+1);
return max(sp[l][lg],sp[r+1-(1<<lg)][lg]);
}
};
struct spmn //sparse table for min
{
int sp[N][LG]={};
spmn(vector<int>vals)
{
int n=vals.size();
for (int i=0;i<n;i++)
sp[i][0]=vals[i];
for (int j=1;(1<<j)<=n;j++)
for (int i=0;i+(1<<j)-1<n;i++)
sp[i][j]=min(sp[i][j-1],sp[i+(1<<(j-1))][j-1]);
}
inline int get(int l,int r)
{
if (l>r)
return 0;
int lg=log2(r-l+1);
return min(sp[l][lg],sp[r+1-(1<<lg)][lg]);
}
};
int l[N][N],r[N][N],u[N][N],d[N][N]={};
int n,m;
vector<spmn>mr,md;
vector<spmx>ml,mu;
inline bool check(int u,int d,int l,int r)
{
if (u==0||d==n-1||l==0||r==m-1)
return 0;
if (md[u-1].get(l,r)<d)
return 0;
if (mu[d+1].get(l,r)>u)
return 0;
if (ml[r+1].get(u,d)>l)
return 0;
if (mr[l-1].get(u,d)<r)
return 0;
return 1;
}
long long count_rectangles(vector<vector<int>>a)
{
n=a.size(),m=a[0].size();
vector<pair<pii,pii>>ans;
for (int i=0;i<n;i++)
{
deque<pair<int,int>>vl;
vl.push_back({-1,1e9});
for (int j=0;j<m;j++)
{
while (vl.size()&&vl.back().second<a[i][j])
vl.pop_back();
l[i][j]=vl.back().first+1;
vl.push_back({j,a[i][j]});
}
vl={};
vl.push_back({m,1e9});
for (int j=m-1;j>=0;j--)
{
while (vl.size()&&vl.back().second<a[i][j])
vl.pop_back();
r[i][j]=vl.back().first-1;
vl.push_back({j,a[i][j]});
}
}
for (int i=0;i<m;i++)
{
deque<pair<int,int>>vl;
vl.push_back({-1,1e9});
for (int j=0;j<n;j++)
{
while (vl.size()&&vl.back().second<a[j][i])
vl.pop_back();
u[j][i]=vl.back().first+1;
vl.push_back({j,a[j][i]});
}
vl={};
vl.push_back({n,1e9});
for (int j=n-1;j>=0;j--)
{
while (vl.size()&&vl.back().second<a[j][i])
vl.pop_back();
d[j][i]=vl.back().first-1;
vl.push_back({j,a[j][i]});
}
}
for (int i=0;i<n;i++)
{
vector<int>u1,d1;
for (int j=0;j<m;j++)
{
u1.push_back(u[i][j]);
d1.push_back(d[i][j]);
}
mu.push_back(spmx(u1));
md.push_back(spmn(d1));
}
for (int i=0;i<m;i++)
{
vector<int>l1,r1;
for (int j=0;j<n;j++)
{
l1.push_back(l[j][i]);
r1.push_back(r[j][i]);
}
ml.push_back(spmx(l1));
mr.push_back(spmn(r1));
}
for (int i=0;i<n;i++)
{
deque<pair<int,int>>vl;
vl.push_back({-1,1e9});
for (int j=0;j<m;j++)
{
while (vl.size()&&vl.back().second<=a[i][j])
vl.pop_back();
l[i][j]=vl.back().first+1;
vl.push_back({j,a[i][j]});
}
vl={};
vl.push_back({m,1e9});
for (int j=m-1;j>=0;j--)
{
while (vl.size()&&vl.back().second<=a[i][j])
vl.pop_back();
r[i][j]=vl.back().first-1;
vl.push_back({j,a[i][j]});
}
}
for (int i=0;i<m;i++)
{
deque<pair<int,int>>vl;
vl.push_back({-1,1e9});
for (int j=0;j<n;j++)
{
while (vl.size()&&vl.back().second<=a[j][i])
vl.pop_back();
u[j][i]=vl.back().first+1;
vl.push_back({j,a[j][i]});
}
vl={};
vl.push_back({n,1e9});
for (int j=n-1;j>=0;j--)
{
while (vl.size()&&vl.back().second<=a[j][i])
vl.pop_back();
d[j][i]=vl.back().first-1;
vl.push_back({j,a[j][i]});
}
}
for (int i=1;i<n-1;i++)
{
for (int j=1;j<m-1;j++)
{
if (check(u[i][j],d[i][j],l[i][j],r[i][j]))
{
ans.push_back({{u[i][j],d[i][j]},{l[i][j],r[i][j]}});
}
}
}
sort(begin(ans),end(ans));
int cnt=0;
for (int i=0;i<ans.size();i++)
{
int j=i;
while (j<ans.size()&&ans[i]==ans[j])
j++;
cnt++;
i=j-1;
}
return cnt;
}
