#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()
#define siz(x) (int)x.size()
#define FOR(x, y, z) for(int x = (y); x < (z); x++)
#define ROF(x, z, y) for(int x = (y-1); x >= (z); x--)
#define F0R(x, z) FOR(x, 0, z)
#define R0F(x, z) ROF(x, 0, z)
#define trav(x, y) for(auto&x:y)
using ll = long long;
using vi = vector<int>;
using vl = vector<long long>;
using pii = pair<int, int>;
using vpii = vector<pair<int, int>>;
template<class T> inline bool ckmin(T&a, T b) {return b < a ? a = b, 1 : 0;}
template<class T> inline bool ckmax(T&a, T b) {return b > a ? a = b, 1 : 0;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const char nl = '\n';
const int mxN = 2e5 + 10;
const int MOD = 1e9 + 7;
const long long infLL = 1e18;
ll count_rectangles(vector<vi> a){
int n = siz(a), m = siz(a[0]); ll ans = 0;
auto precalc = [&](vector<vi> b){
int N = siz(b), M = siz(b[0]);
//F0R(i, N){
// F0R(j, M){
// cout << b[i][j] << ' ';
// }
// cout << nl;
//}
auto go = [&](vi v){
stack<pii> s;
vi res(M);
F0R(i, M){
while(siz(s)&&s.top().f<v[i]){
//cout << s.top().f << ' ' << v[i] << nl;
s.pop();
}
if(!siz(s)) res[i]=-1;
else res[i]=s.top().s;
//cout << res[i] << ' ';
s.push({v[i], i});
}
//cout << nl;
return res;
};
vector<vector<vpii>> res(N, vector<vpii>(M));
F0R(i, N){
//F0R(j, M) cout << b[i][j] << ' ';
//cout << nl;
vi l = go(b[i]);
reverse(all(b[i]));
vi r = go(b[i]);
reverse(all(b[i]));
reverse(all(r));
F0R(j, M){
if(r[j]!=-1) r[j]=M-1-r[j];
//cout << r[j] << ' ';
}
//cout << nl;
F0R(j, M){
//cout << l[j] << ' ';
if(l[j]!=-1&&l[j]!=j-1){
assert(l[j]<=j);
res[i][j-1].pb({l[j]+1, 1});
}
}
//cout << nl << nl;
F0R(j, M){
if(r[j]!=-1&&r[j]!=j+1){
assert(r[j]>=j);
res[i][r[j]-1].pb({j+1, 1});
}
}
F0R(j, M){
sort(all(res[i][j]));
res[i][j].resize(unique(all(res[i][j]))-res[i][j].begin());
}
}
F0R(i, N-1){
F0R(j, M){
trav(x, res[i][j]){
trav(y, res[i+1][j]){
if(x.f==y.f){
y.s = x.s+1;
}
}
}
}
}
return res;
};
vector<vector<vpii>> x = precalc(a);
vector<vi> c(m, vi(n));
F0R(i, n)
F0R(j, m)
c[j][i]=a[i][j];
vector<vector<vpii>> y2 = precalc(c);
vector<vector<vpii>> y(n, vector<vpii>(m));
F0R(i, n)
F0R(j, m)
y[i][j]=y2[j][i];
//F0R(i, n){
// F0R(j, m){
// trav(X, x[i][j]){
// cout << i << ' ' << j << ' ' << X.f << ' ' << X.s << nl;
// }
// }
//}
//cout << nl;
//F0R(i, n){
// F0R(j, m){
// trav(X, y[i][j]){
// cout << i << ' ' << j << ' ' << X.f << ' ' << X.s << nl;
// }
// }
//}
//cout << nl;
F0R(i, n){
F0R(j, m){
trav(v, x[i][j]){
//cout << "V: " << v.f << ' ' << v.s << nl;
trav(v2, y[i][j]){
//cout << i << ' ' << j << ' ' << v.f << ' ' << v.s << ' ' << v2.f << ' ' << v2.s << nl;
if(v.s>=i-v2.f+1&&v2.s>=j-v.f+1) {
ans++;
}
}
}
//trav(v2, y[i][j]){
// cout << "V2: " << v2.f << ' ' << v2.s << nl;
//}
}
}
return ans;
}
//int32_t main(){
// ios_base::sync_with_stdio(0); cin.tie(0);
// int N, M; cin >> N >> M;
// vector<vi> inp(N, vi(M));
// F0R(i, N){
// F0R(j, M){
// cin >> inp[i][j];
// }
// }
// cout << count_rectangles(inp) << nl;
// return 0;
//}
