#include "rect.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define fi first
#define se second
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;
struct NOD {
NOD(int sy, int sx, int ey, int ex)
: sy(sy), sx(sx), ey(ey), ex(ex) {}
int sy, sx, ey, ex;
void f(int &_sy, int &_sx, int &_ey, int &_ex) const {
_sy = sy; _sx = sx; _ey = ey; _ex = ex;
}
bool operator < (const NOD &t) const {
if(sy != t.sy) return sy < t.sy;
if(sx != t.sx) return sx < t.sx;
if(ey != t.ey) return ey < t.ey;
return ex < t.ex;
}
bool operator == (const NOD &t) const {
return sy == t.sy && sx == t.sx && ey == t.ey && ex == t.ex;
}
};
const int MX = 4096;
struct SEG {
SEG() { init(); }
int d[MX*2];
void init() { fill(d, d+MX*2, INF); }
void upd(int x, int r) { upmin(d[x+MX], r); }
void cal() { for(int i = MX; i--;) d[i] = min(d[i<<1], d[i<<1|1]); }
int get(int s, int e) {
int r = INF; for(s += MX, e += MX; s <= e; s >>= 1, e >>= 1) {
if(s&1) upmin(r, d[s++]);
if(~e&1) upmin(r, d[e--]);
}
return r;
}
} segu[2505], segd[2505], segl[2505], segr[2505];
vector<NOD> NV;
int myu[2505][2505], myd[2505][2505], myl[2505][2505], myr[2505][2505];
int cou[2505][2505], cod[2505][2505], col[2505][2505], cor[2505][2505];
int A[2505][2505];
int H, W, Ans;
int solve() {
for(int j = 0; j < W; j++) {
vector<pii> V; V.eb(-1, INF);
for(int i = 0, h; i < H; i++) {
for(h = A[i][j]; V.back().se <= h; V.pop_back());
myu[i][j] = V.back().fi;
V.eb(i, h);
}
V.clear(); V.eb(H, INF);
for(int i = H, h; i--;) {
for(h = A[i][j]; V.back().se <= h; V.pop_back());
myd[i][j] = V.back().fi;
V.eb(i, h);
}
V.clear(); V.eb(-1, INF);
for(int i = 0, h; i < H; i++) {
for(h = A[i][j]; V.back().se < h; V.pop_back());
cou[i][j] = V.back().fi + 1;
V.eb(i, h);
}
V.clear(); V.eb(H, INF);
for(int i = H, h; i--;) {
for(h = A[i][j]; V.back().se < h; V.pop_back());
cod[i][j] = V.back().fi - 1;
V.eb(i, h);
}
}
for(int i = 0; i < H; i++) {
vector<pii> V; V.eb(-1, INF);
for(int j = 0, h; j < W; j++) {
for(h = A[i][j]; V.back().se <= h; V.pop_back());
myl[i][j] = V.back().fi;
V.eb(j, h);
}
V.clear(); V.eb(W, INF);
for(int j = W, h; j--;) {
for(h = A[i][j]; V.back().se <= h; V.pop_back());
myr[i][j] = V.back().fi;
V.eb(j, h);
}
V.clear(); V.eb(-1, INF);
for(int j = 0, h; j < W; j++) {
for(h = A[i][j]; V.back().se < h; V.pop_back());
col[i][j] = V.back().fi + 1;
V.eb(j, h);
}
V.clear(); V.eb(W, INF);
for(int j = W, h; j--;) {
for(h = A[i][j]; V.back().se < h; V.pop_back());
cor[i][j] = V.back().fi - 1;
V.eb(j, h);
}
}
for(int i = 0; i < H; i++) for(int j = 0; j < W; j++) {
segu[i].upd(j, -cou[i][j]);
segd[i].upd(j, cod[i][j]);
segl[j].upd(i, -col[i][j]);
segr[j].upd(i, cor[i][j]);
}
for(int i = 0; i < H; i++) { segu[i].cal(); segd[i].cal(); }
for(int i = 0; i < W; i++) { segl[i].cal(); segr[i].cal(); }
for(int i = 1; i < H-1; i++) for(int j = 1; j < W-1; j++) {
int sy = myu[i][j] + 1, sx = myl[i][j] + 1, ey = myd[i][j] - 1, ex = myr[i][j] - 1;
if(!sy || !sx || H-1 == ey || W-1 == ex) continue;
NV.eb(sy, sx, ey, ex);
}
sorv(NV); univ(NV);
for(auto &hubo : NV) {
int sy, sx, ey, ex; hubo.f(sy, sx, ey, ex);
if(sy < -segu[ey+1].get(sx, ex)) continue;
if(segd[sy-1].get(sx, ex) < ey) continue;
if(sx < -segl[ex+1].get(sy, ey)) continue;
if(segr[sx-1].get(sy, ey) < ex) continue;
Ans++;
}
return Ans;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
::H = sz(a); ::W = sz(a[0]);
for(int i = 0; i < ::H; i++) for(int j = 0; j < ::W; j++)
::A[i][j] = a[i][j];
return solve();
}
