#include "rect.h"
#include <bits/stdc++.h>
#define SZ 2501
using namespace std;
struct rect
{
int x1, x2, y1, y2;
};
int r[SZ][SZ], l[SZ][SZ], u[SZ][SZ], d[SZ][SZ];
int N, M;
stack<pair<int, int> > st;
vector<int> row[SZ][SZ], col[SZ][SZ];
vector<rect> ret;
bool comp(rect a, rect b)
{
if (a.x1==b.x1 && a.x2==b.x2 && a.y1==b.y1) return a.y2<b.y2;
if (a.x1==b.x1 && a.x2==b.x2) return a.y1<b.y1;
if (a.x1==b.x1) return a.x2<b.x2;
return a.x1<b.x1;
}
long long count_rectangles(vector<vector<int> > a)
{
N=a.size(), M=a[0].size();
long long ans=0;
int idx1, idx2, X1, X2, Y1, Y2;
for (int i=0; i<N; i++) {
st.push({0, a[i][0]});
for (int j=1; j<M; j++) {
while (!st.empty()) {
if (a[i][j]>=st.top().second) st.pop();
else break;
}
if (st.empty()) l[i][j]=-1;
else l[i][j]=st.top().first;
st.push({j, a[i][j]});
}
while (!st.empty()) st.pop();
st.push({M-1, a[i][M-1]});
for (int j=M-2; j>=0; j--) {
while (!st.empty()) {
if (a[i][j]>=st.top().second) st.pop();
else break;
}
if (st.empty()) r[i][j]=-1;
else r[i][j]=st.top().first;
st.push({j, a[i][j]});
}
while (!st.empty()) st.pop();
}
for (int i=0; i<M; i++) {
while (!st.empty()) st.pop();
st.push({0, a[0][i]});
for (int j=1; j<N; j++) {
while (!st.empty()) {
if (a[j][i]>=st.top().second) st.pop();
else break;
}
if (st.empty()) u[j][i]=-1;
else u[j][i]=st.top().first;
st.push({j, a[j][i]});
}
while (!st.empty()) st.pop();
st.push({N-1, a[N-1][i]});
for (int j=N-2; j>=0; j--) {
while (!st.empty()) {
if (a[j][i]>=st.top().second) st.pop();
else break;
}
if (st.empty()) d[j][i]=-1;
else d[j][i]=st.top().first;
st.push({j, a[j][i]});
}
}
for (int i=1; i<N-1; i++) for (int j=1; j<M-1; j++) if (r[i][j]!=-1 && l[i][j]!=-1) {
Y1=l[i][j]+1, Y2=r[i][j]-1;
if (!(!row[Y1][Y2].empty() && row[Y1][Y2][row[Y1][Y2].size()-1]==i)) row[Y1][Y2].push_back(i);
}
for (int j=1; j<M-1; j++) for (int i=1; i<N-1; i++) if (u[i][j]!=-1 && d[i][j]!=-1) {
X1=u[i][j]+1, X2=d[i][j]-1;
if (!(!col[X1][X2].empty() && col[X1][X2][col[X1][X2].size()-1]==j)) col[X1][X2].push_back(j);
}
for (int i=1; i<N-1; i++) for (int j=1; j<M-1; j++) if (r[i][j]!=-1 && l[i][j]!=-1 && u[i][j]!=-1 && d[i][j]!=-1) {
X1=u[i][j]+1, X2=d[i][j]-1, Y1=l[i][j]+1, Y2=r[i][j]-1;
idx1=lower_bound(row[Y1][Y2].begin(), row[Y1][Y2].end(), X1)-row[Y1][Y2].begin();
idx2=lower_bound(col[X1][X2].begin(), col[X1][X2].end(), Y1)-col[X1][X2].begin();
if (row[Y1][Y2][idx1]==X1 && col[X1][X2][idx2]==Y1) {
if ((idx1+X2-X1<=row[Y1][Y2].size() && row[Y1][Y2][idx1+X2-X1]==X2) && (idx2+Y2-Y1<=col[X1][X2].size() && col[X1][X2][idx2+Y2-Y1]==Y2)) {
rect temp;
temp.x1=X1, temp.x2=X2, temp.y1=Y1, temp.y2=Y2;
ret.push_back(temp);
}
}
}
X1=X2=Y1=Y2=-1;
sort(ret.begin(), ret.end(), comp);
for (auto i : ret) {
if (X1==i.x1 && X2==i.x2 && Y1==i.y1 && Y2==i.y2) continue;
else {
X1=i.x1, X2=i.x2, Y1=i.y1, Y2=i.y2;
//printf("%d %d %d %d\n", X1, X2, Y1, Y2);
ans++;
}
}
return ans;
}
