//
// I have a dream and a piano
//
#include <bits/stdc++.h>
#define FAST ios::sync_with_stdio(0),cin.tie(0)
#define Loop(x,l,r) for(int x=(l);x<(r);++x)
#define LoopR(x,l,r) for(int x=(r)-1;x>=(l);--x)
#define all(v) v.begin(),v.end()
typedef std::pair<int,int> pii;
typedef long long ll;
using namespace std;
const int N = 2520;
int a[N][N];
int b[N][N];
int n, m;
short lg[N][N], rg[N][N], dg[N][N], ug[N][N];
short lnl[N][N], rnl[N][N], dnl[N][N], unl[N][N];
short lnlr[N][N], rnlr[N][N], dnlr[N][N], unlr[N][N];
template<class Cmp_fn> void mk_nxt(short* di, int* si, int n, Cmp_fn f){
vector<int> st;
Loop(i,0,n){
while(st.size() && !f(si[st.back()], si[i])) st.pop_back();
di[i] = st.size()? i-st.back(): i+1;
st.push_back(i);
}
}
template<class Cmp_fn> void mk_nxt_rv(short* di, int* si, int n, Cmp_fn f){
vector<int> st;
LoopR(i,0,n){
while(st.size() && !f(si[st.back()], si[i])) st.pop_back();
di[i] = st.size()? st.back()-i: n-i;
st.push_back(i);
}
}
void init_g_nl()
{
Loop(i,0,n)
mk_nxt(lg[i] , a[i], m, greater<int>()),
mk_nxt(lnl[i], a[i], m, greater_equal<int>()),
mk_nxt_rv(rg[i] , a[i], m, greater<int>()),
mk_nxt_rv(rnl[i], a[i], m, greater_equal<int>());
Loop(j,0,m)
mk_nxt(ug[j] , b[j], n, greater<int>()),
mk_nxt(unl[j], b[j], n, greater_equal<int>()),
mk_nxt_rv(dg[j] , b[j], n, greater<int>()),
mk_nxt_rv(dnl[j], b[j], n, greater_equal<int>());
Loop(i,0,n) Loop(j,0,m)
lnlr[j][i] = lnl[i][j],
rnlr[j][i] = rnl[i][j],
unlr[i][j] = unl[j][i],
dnlr[i][j] = dnl[j][i];
}
struct RMQ
{
int size;
short a[N<<2];
void init_(short* si, int i, int b, int e)
{
if(e-b==1) {a[i] = si[b]; return;}
init_(si,2*i+1,b,(b+e)/2);
init_(si,2*i+2,(b+e)/2,e);
a[i] = min(a[2*i+1], a[2*i+2]);
}
short get_(int l, int r, int i, int b, int e)
{
if(l <= b && e <= r) return a[i];
short ans = N+10;
if(l < (b+e)/2) ans = min(ans, get_(l,r,2*i+1,b,(b+e)/2));
if((b+e)/2 < r) ans = min(ans, get_(l,r,2*i+2,(b+e)/2,e));
return ans;
}
void init(short* si, int n){size=n; init_(si,0,0,size);}
short get(int l, int r){return get_(l,r,0,0,size);}
};
RMQ mlnl[N], mrnl[N], mdnl[N], munl[N];
void init_rmq(){
Loop(i,0,m)
mlnl[i].init(lnlr[i], n),
mrnl[i].init(rnlr[i], n);
Loop(i,0,n)
munl[i].init(unlr[i], m),
mdnl[i].init(dnlr[i], m);
}
typedef tuple<int,int,int,int> tup;
bool good(int i, int j, tup& t)
{
int l = j-lg[i][j], r = rg[i][j]+j;
int u = i-ug[j][i], d = dg[j][i]+i;
t = {l,r,u,d};
if(l == -1 || r == m || u == -1 || d == n) return 0;
if(mdnl[u].get(l+1, r) < d-u) return 0;
if(munl[d].get(l+1, r) < d-u) return 0;
if(mrnl[l].get(u+1, d) < r-l) return 0;
if(mlnl[r].get(u+1, d) < r-l) return 0;
return 1;
}
#include <ext/pb_ds/assoc_container.hpp>
struct chash
{
size_t operator()(ll x) const
{
size_t FIXED_RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
size_t ans = x + FIXED_RANDOM;
ans += 0x786f3d7a52f61cb7;
ans = (ans ^ (ans >> 27)) * 0x881734ab36fce91b;
ans = (ans ^ (ans >> 31)) * 0x5256bce6ad237463;
return ans ^ (ans >> 30);
}
};
unordered_set<ll> cnted;
ll tup2qw(tup x){return get<0>(x)+((ll)get<1>(x)<<16)+((ll)get<2>(x)<<32)+((ll)get<3>(x)<<48);}
ll count_rectangles(vector<vector<int>> v)
{
n = v.size(); m = v[0].size();
Loop(i,0,n) Loop(j,0,m) b[j][i] = a[i][j] = v[i][j];
init_g_nl();
init_rmq();
ll ans = 0;
Loop(i,0,n) Loop(j,0,m)
{
tup t;
if(good(i,j,t))
{
ll qw = tup2qw(t);
if(cnted.find(qw) != cnted.end()) continue;
++ans;
cnted.insert(qw);
}
}
return ans;
}
//int main(){cout << count_rectangles({{4, 8, 7, 5, 6},{7, 4, 10, 3, 5},{9, 7, 20, 14, 2},{9, 14, 7, 3, 6},{5, 7, 5, 2, 7},{4, 5, 13, 5, 6}}) << '\n';}
