#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
const int mxN=2505;
typedef struct rect{
short x1, x2, y1, y2;
rect() : x1(0), x2(0), y1(0), y2(0) {}
rect(short x1, short x2, short y1, short y2) : x1(x1), x2(x2), y1(y1), y2(y2) {}
bool operator==(rect a)
{
return (a.x1==x1 && a.x2==x2 && a.y1==y1 && a.y2==y2);
}
}rect;
typedef struct qry{
short s, e, rowcol;
int idx;
qry() : s(0), e(0), rowcol(0), idx(0) {}
qry(short s, short e, short rowcol, int idx) : s(s), e(e), rowcol(rowcol), idx(idx) {}
}qry;
short N, M;
int A[mxN][mxN];
short L[mxN][mxN], R[mxN][mxN], U[mxN][mxN], D[mxN][mxN];
vector <rect> v;
bool Chk[mxN*mxN];
vector <qry> cont[4][mxN];
bool cmp1(rect a, rect b)
{
if(a.x1!=b.x1) return a.x1<b.x1;
if(a.x2!=b.x2) return a.x2<b.x2;
if(a.y1!=b.y1) return a.y1<b.y1;
return a.y2<b.y2;
}
void make_LRUD1()
{
for(short i=1;i<N-1;i++)
{
stack <short> stk;
for(short j=0;j<M;j++)
{
while(!stk.empty() && A[i][stk.top()]<=A[i][j]) stk.pop();
L[i][j]=(stk.empty() ? -1 : stk.top());
stk.push(j);
}
while(!stk.empty()) stk.pop();
for(short j=M-1;j>=0;j--)
{
while(!stk.empty() && A[i][stk.top()]<=A[i][j]) stk.pop();
R[i][j]=(stk.empty() ? M : stk.top());
stk.push(j);
}
}
for(short i=1;i<M-1;i++)
{
stack <short> stk;
for(short j=0;j<N;j++)
{
while(!stk.empty() && A[stk.top()][i]<=A[j][i]) stk.pop();
U[j][i]=(stk.empty() ? -1 : stk.top());
stk.push(j);
}
while(!stk.empty()) stk.pop();
for(short j=N-1;j>=0;j--)
{
while(!stk.empty() && A[stk.top()][i]<=A[j][i]) stk.pop();
D[j][i]=(stk.empty() ? N : stk.top());
stk.push(j);
}
}
}
void make_LRUD2()
{
for(short i=1;i<N-1;i++)
{
stack <short> stk;
for(short j=0;j<M;j++)
{
while(!stk.empty() && A[i][stk.top()]<A[i][j]) stk.pop();
L[i][j]=(stk.empty() ? -1 : stk.top());
stk.push(j);
}
while(!stk.empty()) stk.pop();
for(short j=M-1;j>=0;j--)
{
while(!stk.empty() && A[i][stk.top()]<A[i][j]) stk.pop();
R[i][j]=(stk.empty() ? M : stk.top());
stk.push(j);
}
}
for(short i=1;i<M-1;i++)
{
stack <short> stk;
for(short j=0;j<N;j++)
{
while(!stk.empty() && A[stk.top()][i]<A[j][i]) stk.pop();
U[j][i]=(stk.empty() ? -1 : stk.top());
stk.push(j);
}
while(!stk.empty()) stk.pop();
for(short j=N-1;j>=0;j--)
{
while(!stk.empty() && A[stk.top()][i]<A[j][i]) stk.pop();
D[j][i]=(stk.empty() ? N : stk.top());
stk.push(j);
}
}
}
short seg[4*mxN];
void init(short idx, short s, short e, short lrud, short rowcol) ///DURL
{
if(s==e)
{
if(lrud==0) seg[idx]=D[rowcol][s];
if(lrud==1) seg[idx]=U[rowcol][s];
if(lrud==2) seg[idx]=R[s][rowcol];
if(lrud==3) seg[idx]=L[s][rowcol];
return;
}
short mid=(s+e)/2;
init(2*idx, s, mid, lrud, rowcol);
init(2*idx+1, mid+1, e, lrud, rowcol);
if(lrud==0 || lrud==2) seg[idx]=min(seg[2*idx], seg[2*idx+1]);
else seg[idx]=max(seg[2*idx], seg[2*idx+1]);
}
short lim;
bool typ;
bool solv(short idx, short s1, short e1, short s2, short e2)
{
if(typ ? seg[idx]<=lim : seg[idx]>=lim) return true;
if(s2<=s1 && e1<=e2) return (typ ? seg[idx]<=lim : seg[idx]>=lim);
short mid=(s1+e1)/2;
if(e2<=mid) return solv(2*idx, s1, mid, s2, e2);
if(s2>mid) return solv(2*idx+1, mid+1, e1, s2, e2);
return (solv(2*idx, s1, mid, s2, e2) && solv(2*idx+1, mid+1, e1, s2, e2));
}
void make_seg()
{
for(short i=0;i<N;i++)
{
init(1, 0, M-1, 0, i); typ=false;
for(auto ele : cont[0][i])
{
lim=ele.rowcol;
if(!solv(1, 0, M-1, ele.s, ele.e)) Chk[ele.idx]=false;
}
init(1, 0, M-1, 1, i); typ=true;
for(auto ele : cont[1][i])
{
lim=ele.rowcol;
if(!solv(1, 0, M-1, ele.s, ele.e)) Chk[ele.idx]=false;
}
}
for(short i=0;i<M;i++)
{
init(1, 0, N-1, 2, i); typ=false;
for(auto ele : cont[2][i])
{
lim=ele.rowcol;
if(!solv(1, 0, N-1, ele.s, ele.e)) Chk[ele.idx]=false;
}
init(1, 0, N-1, 3, i); typ=true;
for(auto ele : cont[3][i])
{
lim=ele.rowcol;
if(!solv(1, 0, N-1, ele.s, ele.e)) Chk[ele.idx]=false;
}
}
}
long long count_rectangles(std::vector<std::vector<int> > a) {
N=a.size();
M=a[0].size();
for(short i=0;i<N;i++) for(short j=0;j<M;j++) A[i][j]=a[i][j];
make_LRUD1();
for(short i=1;i<N-1;i++)
{
for(short j=1;j<M-1;j++)
{
if(U[i][j]!=-1 && D[i][j]!=N && L[i][j]!=-1 && R[i][j]!=M) v.emplace_back(U[i][j]+1, D[i][j]-1, L[i][j]+1, R[i][j]-1);
}
}
sort(v.begin(), v.end(), cmp1);
v.erase(unique(v.begin(), v.end()), v.end());
make_LRUD2();
for(int i=0;i<v.size();i++)
{
rect ele=v[i];
Chk[i]=true;
cont[0][ele.x1-1].emplace_back(ele.y1, ele.y2, ele.x2+1, i);
cont[1][ele.x2+1].emplace_back(ele.y1, ele.y2, ele.x1-1, i);
cont[2][ele.y1-1].emplace_back(ele.x1, ele.x2, ele.y2+1, i);
cont[3][ele.y2+1].emplace_back(ele.x1, ele.x2, ele.y1-1, i);
}
make_seg();
int ans=0;
for(int i=0;i<v.size();i++) ans+=Chk[i];
return ans;
}
