#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC target("avx,avx2,fma")
#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]);
auto go = [&](vi v){
stack<pii> s;
vpii res(M);
F0R(i, M){
while(siz(s)&&s.top().f<v[i]){
s.pop();
}
if(!siz(s)) res[i]={-1, 0};
else res[i]={s.top().s, 1};
s.push({v[i], i});
}
return res;
};
vector<vector<vpii>> res(N, vector<vpii>(M));
vpii lastl, lastr;
F0R(i, N){
vpii l = go(b[i]);
reverse(all(b[i]));
vpii r = go(b[i]);
reverse(all(b[i]));
reverse(all(r));
F0R(j, M){
if(r[j].f!=-1) r[j].f=M-1-r[j].f;
}
if(i==0) goto skip;
F0R(j, M){
if(r[j].f==lastr[j].f&&r[j].f!=-1) r[j].s=lastr[j].s+1;
}
F0R(j, M){
if(l[j].f==lastl[j].f&&l[j].f!=-1) l[j].s=lastl[j].s+1;
}
skip:;
F0R(j, M){
if(l[j].f!=-1&&l[j].f!=j-1){
res[i][j-1].pb({l[j].f+1, l[j].s});
}
}
F0R(j, M){
if(r[j].f!=-1&&r[j].f!=j+1){
res[i][r[j].f-1].pb({j+1, r[j].s});
}
}
F0R(j, M){
sort(all(res[i][j]));
res[i][j].resize(unique(all(res[i][j]))-res[i][j].begin());
}
lastl = l, lastr = r;
}
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(v, x[i][j]){
trav(v2, y[i][j]){
if(v.s>=i-v2.f+1&&v2.s>=j-v.f+1) {
ans++;
}
}
}
}
}
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;
//}
