#include "rect.h"
#include "bits/stdc++.h"
using namespace std;
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
using ll=int;
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<short,short>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>;
long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (2503)
ll r, c, A[MAXN][MAXN];
struct grid {
short r, l, u, d;
} G[MAXN][MAXN], P[MAXN][MAXN];
set<dpi> s;
short tmp[MAXN], pre[MAXN];
struct _st {
short st[12][MAXN];
void build() {
FOR(i,1,MAXN-1) st[0][i]=tmp[i];
FOR(h,1,11) for(ll i=1;i+(1<<h)-1<MAXN;++i) {
st[h][i] = min(st[h-1][i], st[h-1][i+(1<<(h-1))]);
}
}
/*int lg2(int x) {
return 31 ^ __builtin_clz(x); // ll has 2^64 - 1 so 63 bits
}*/
short query(int x, int y) { // inclusive in this case
short p = pre[y-x+1];
return min(st[p][x], st[p][y-(1<<p)+1]);
}
} R[MAXN], L[MAXN], U[MAXN], D[MAXN];
// #define gc getchar_unlocked
// inline ll in() {
// char ch=gc();
// ll x=0;
// while(ch<'0'||ch>'9') ch=gc();
// while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch&15),ch=gc();
// return x;
// }
int main2() {
FOR(i,0,2500) pre[i] = 31 ^ __builtin_clz(i);
// FAST
// r=in(), c=in();
// FOR(i,1,r) FOR(j,1,c) A[i][j]=in();
vector<pair<int, short>> v;
FOR(j,1,c) {
v.clear();
vector<pair<ll, short>>().swap(v);
DEC(i,r,1) {
while(v.size() && v.back().f < A[i][j]) v.pop_back();
G[i][j].d = v.size() ? v.back().s : r + 1;
v.eb(A[i][j], i);
}
}
FOR(j,1,c) {
v.clear();
vector<pair<ll, short>>().swap(v);
FOR(i,1,r) {
while(v.size() && v.back().f < A[i][j]) v.pop_back();
G[i][j].u = v.size() ? v.back().s : 0;
v.eb(A[i][j], i);
}
}
FOR(i,1,r) {
v.clear();
vector<pair<ll, short>>().swap(v);
DEC(j,c,1) {
while(v.size() && v.back().f < A[i][j]) v.pop_back();
G[i][j].r = v.size() ? v.back().s : c + 1;
v.eb(A[i][j], j);
}
}
FOR(i,1,r) {
v.clear();
vector<pair<ll, short>>().swap(v);
FOR(j,1,c) {
while(v.size() && v.back().f < A[i][j]) v.pop_back();
G[i][j].l = v.size() ? v.back().s : 0;
v.eb(A[i][j], j);
}
}
FOR(j,1,c) {
v.clear();
vector<pair<ll, short>>().swap(v);
DEC(i,r,1) {
while(v.size() && v.back().f < A[i][j]) v.pop_back();
P[i][j].d = v.size() ? v.back().s : r + 1;
v.eb(A[i][j], i);
}
}
FOR(j,1,c) {
v.clear();
vector<pair<ll, short>>().swap(v);
FOR(i,1,r) {
while(v.size() && v.back().f <= A[i][j]) v.pop_back();
P[i][j].u = v.size() ? v.back().s : 0;
v.eb(A[i][j], i);
}
}
FOR(i,1,r) {
v.clear();
vector<pair<ll, short>>().swap(v);
DEC(j,c,1) {
while(v.size() && v.back().f < A[i][j]) v.pop_back();
P[i][j].r = v.size() ? v.back().s : c + 1;
v.eb(A[i][j], j);
}
}
FOR(i,1,r) {
v.clear();
vector<pair<ll, short>>().swap(v);
FOR(j,1,c) {
while(v.size() && v.back().f <= A[i][j]) v.pop_back();
P[i][j].l = v.size() ? v.back().s : 0;
v.eb(A[i][j], j);
}
}
// FOR(i,1,r) {
// FOR(j,0,MAXN-1) tmp[j] = A[i][j];
// row[i].build();
// }
// FOR(j,1,c) {
// FOR(i,0,MAXN-1) tmp[i] = A[i][j];
// col[j].build();
// }
FOR(i,1,r) {
FOR(j,0,MAXN-1) tmp[j] = -G[i][j].u;
U[i].build();
FOR(j,0,MAXN-1) tmp[j] = G[i][j].d;
D[i].build();
}
FOR(j,1,c) {
FOR(i,0,MAXN-1) tmp[i] = G[i][j].r;
R[j].build();
FOR(i,0,MAXN-1) tmp[i] = -G[i][j].l;
L[j].build();
}
int ans = 0;
v.clear();
vector<pair<ll, short>>().swap(v);
FOR(i,1,r)FOR(j,1,c){
short r1,c1,r2,c2;
r1 = P[i][j].u, r2 = P[i][j].d, c1 = P[i][j].l, c2 = P[i][j].r;
if(r1 == 0 || r2 == r + 1 || c1 == 0 || c2 == c+1 || s.find(dpi(pi(r1, c1),pi(r2, c2))) != s.end()) continue;
s.ins(dpi(pi(r1, c1),pi(r2, c2)));
bool okay = 1;
// FOR(r,r1+1,r2-1) okay &= A[r][c1] > A[i][j], okay &= A[r][c2] > A[i][j],
// okay &= G[r][c1].r >= c2, okay &= G[r][c2].l <= c1;
// okay &= col[c1].query(r1+1, r2-1) > A[i][j], okay &= col[c2].query(r1+1, r2-1) > A[i][j];
okay &= R[c1].query(r1+1, r2-1) >= c2, okay &= -L[c2].query(r1+1, r2-1) <= c1;
// FOR(c,c1+1,c2-1) okay &= A[r1][c] > A[i][j], okay &= A[r2][c] > A[i][j],
// okay &= G[r1][c].d >= r2, okay &= G[r2][c].u <= r1;
// okay &= row[r1].query(c1+1, c2-1) > A[i][j], okay &= row[r2].query(c1+1, c2-1) > A[i][j];
okay &= D[r1].query(c1+1, c2-1) >= r2, okay &= -U[r2].query(c1+1, c2-1) <= r1;
ans += okay;
// if(okay) {
// cerr<<r1<<' '<<c1<<' '<<r2<<' '<<c2<<' '<<i<<' '<<j<<'\n';
// }
}
return ans;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
r = siz(a), c = siz(a[0]);
FOR(i,1,r)FOR(j,1,c)A[i][j]=a[i-1][j-1];
a.clear(), vector<vector<int>>().swap(a);
return main2();
}
