//
// 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;
const int lgN = 13;
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
{
short a[lgN][N];
void init(short* si, int n)
{
memcpy(a[0], si, n*4);
Loop(k,0,lgN-1)
Loop(i,0,n+1-(2<<k))
a[k+1][i] = min(a[k][i], a[k][i+(1<<k)]);
}
int get(int l, int r)
{
int k = 31 - __builtin_clz(r-l);
return min(a[k][l], a[k][r-(1<<k)]);
}
};
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;
}
set<tup> cnted;
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))
{
if(cnted.count(t)) continue;
++ans;
cnted.insert(t);
}
}
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';}
