#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
const int mxN=2505;
typedef struct rect{
int x1, x2, y1, y2;
rect() : x1(0), x2(0), y1(0), y2(0) {}
rect(int x1, int x2, int y1, int 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;
int N, M;
int A[mxN][mxN];
int L[mxN][mxN], R[mxN][mxN], U[mxN][mxN], D[mxN][mxN];
vector <rect> v;
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(int i=1;i<N-1;i++)
{
stack <int> stk;
for(int 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(int 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(int i=1;i<M-1;i++)
{
stack <int> stk;
for(int 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(int 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(int i=1;i<N-1;i++)
{
stack <int> stk;
for(int 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(int 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(int i=1;i<M-1;i++)
{
stack <int> stk;
for(int 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(int 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);
}
}
}
long long count_rectangles(std::vector<std::vector<int> > a) {
N=a.size();
M=a[0].size();
for(int i=0;i<N;i++) for(int j=0;j<M;j++) A[i][j]=a[i][j];
make_LRUD1();
for(int i=1;i<N-1;i++)
{
for(int 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();
int ans=0;
for(auto ele : v)
{
bool ok=true;
for(int i=ele.x1;i<=ele.x2;i++) if(R[i][ele.y1-1]<=ele.y2 || L[i][ele.y2+1]>=ele.y1) ok=false;
for(int i=ele.y1;i<=ele.y2;i++) if(D[ele.x1-1][i]<=ele.x1 || U[ele.x2+1][i]>=ele.x2) ok=false;
if(ok) ans++;
}
return ans;
}
