#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 4e3 + 7;
const int Mod = 1e9 + 7;///lon
const int INF = 1e9 + 7;
const int BASE = 137;
const int szBL = 350;
int n, m;
int a[N][N];
namespace sub5 {
ll solution() {
vector<vector<int>> toD(n + 1, vector<int> (m + 1, 0)),
toU(n + 1, vector<int> (m + 1, 0)); ///hàng
rep (j, 1, m) {
stack<pii> st;
rep (i, 1, n) {
while (!st.empty() && st.top().fs < a[i][j]) st.pop();
if (!st.empty()) toU[i][j] = st.top().se + 1;
else toU[i][j] = 1;
st.push({a[i][j], i});
}
stack<pii> ().swap(st);
reb (i, n, 1) {
while (!st.empty() && st.top().fs < a[i][j]) st.pop();
if (!st.empty()) toD[i][j] = st.top().se - 1;
else toD[i][j] = n;
st.push({a[i][j], i});
}
}
int res = 0;
vector<int> mxR(n + 3, 0), Down(n + 3, n), Up(n + 3, 1);
rep (j, 1, m) {
rep (i, 1, n)
mxR[i] = 0, Down[i] = n, Up[i] = 1;
reb (k, j - 1, 1) {
int bound = n;
reb (i, n, 1) {
if (Down[i] < bound && Down[i] > i) {
if (Up[Down[i] + 1] <= i + 1) {
++res;
}
}
if (mxR[i] >= min(a[i][j], a[i][k])) {
bound = i;
}
}
bound = 1;
rep (i, 1, n) {
if (Up[i] > bound && Up[i] < i) {
// cout << j <<" "<<k<<" "<<i<<" "<<Up[i] - 1 <<" dasaa\n";
if (Down[Up[i] - 1] >= i) {
++res;
}
}
if (mxR[i] >= min(a[i][j], a[i][k])) {
bound = i;
}
}
///update
rep (i, 1, n) {
mxR[i] = max(mxR[i], a[i][k]);
Down[i] = min(Down[i], toD[i][k]);
Up[i] = max(Up[i], toU[i][k]);
}
}
}
return res;
// cout << res <<"\n";
}
}
ll count_rectangles (vector<vector<int>> A) {
n = SZ(A);
m = SZ(A[0]);
rep (i, 1, n)
rep (j, 1, m) a[i][j] = A[i - 1][j - 1];
return sub5 :: solution();
}
void solution () {
// 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}});
// return;
cin >> n >> m;
rep (i, 1, n)
rep (j, 1, m) cin >> a[i][j];
if (n * m <= 490000) sub5 :: solution();
}
//#define file(name) freopen(name".inp","r",stdin); freopen(name".out","w",stdout);
//main () {
//// file("c");
// ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
// int num_Test = 1;
//// cin >> num_Test;
// while (num_Test--)
// solution();
//}
/*
no bug challenge +15
gọi sao cho có lợi cho mình nhất
*/
