#include <bits/stdc++.h>
#ifndef LOCAL
#include "rect.h"
#endif
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define Time (clock() * 1.0 / CLOCKS_PER_SEC)
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
return y > x ? (x = y, true) : false;
}
void debug_out() {
cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
cerr << ' ' << A;
debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
for (int i = 0; i < n; ++i)
cerr << a[i] << ' ';
cerr << endl;
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
#define debug(...) 1337
#define mdebug(a, n) 1337
#endif
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
for (auto& x : v)
stream << x << ' ';
return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
return stream << p.first << ' ' << p.second;
}
const int INF32 = 1e9;
const int maxN = 2503;
bool badc[maxN];
int a[maxN][maxN];
int L[maxN], R[maxN];
int stk[maxN][maxN], sz[maxN];
namespace fnw {
const int N = 7e2 + 5;
int f[N][N];
void add(int i0, int j0, int delta) {
for (int i = i0 + 1; i < N; i += i & -i)
for (int j = j0 + 1; j < N; j += j & -j)
f[i][j] += delta;
}
int gt(int i0, int j0) {
int res = 0;
for (int i = i0 + 1; i >= 1; i -= i & -i)
for (int j = j0 + 1; j >= 1; j -= j & -j)
res += f[i][j];
return res;
}
}
ll count_rectangles(vector<vector<int>> _a) {
int n = _a.size(), m = _a[0].size();
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
a[i][j] = _a[i][j];
if (min(n, m) < 3) return 0;
ll ans = 0;
for (int r1 = 1; r1 < n - 1; ++r1) {
for (int r2 = r1; r2 < n - 1; ++r2) {
badc[0] = badc[m - 1] = 1;
for (int c = 1; c < m - 1; ++c) {
int mx = -INF32;
for (int i = r1; i <= r2; ++i)
chkmax(mx, a[i][c]);
badc[c] = mx >= min(a[r1 - 1][c], a[r2 + 1][c]);
}
// count L
for (int r = r1; r <= r2; ++r) {
sz[r] = 0;
}
for (int c = 0; c < m; ++c) {
L[c] = 0;
for (int r = r1; r <= r2; ++r) {
while (sz[r] && a[r][stk[r][sz[r] - 1]] < a[r][c]) {
--sz[r];
}
if (sz[r])
chkmax(L[c], stk[r][sz[r] - 1]);
stk[r][sz[r]++] = c;
}
}
// count R
for (int r = r1; r <= r2; ++r) {
sz[r] = 0;
}
for (int c = m - 1; c >= 0; --c) {
R[c] = m;
for (int r = r1; r <= r2; ++r) {
while (sz[r] && a[r][stk[r][sz[r] - 1]] < a[r][c]) {
--sz[r];
}
if (sz[r])
chkmin(R[c], stk[r][sz[r] - 1]);
stk[r][sz[r]++] = c;
}
}
int b = m - 1;
for (int c = m - 2; c >= 0; --c) {
ans += fnw::gt(min(b, R[c]), c);
// for (int d = c + 2; d <= min(b, R[c]); ++d) {
// ans += L[d] <= c;
// }
if (badc[c]) {
b = c;
}
// add c + 1
fnw::add(c + 1, L[c + 1], +1);
}
for (int c = 1; c < m; ++c)
fnw::add(c, L[c], -1);
}
}
return ans;
}
#ifdef LOCAL
int main() {
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
// InputReader inputReader(STDIN_FILENO);
int n, m;
cin >> n >> m;
// n = inputReader.readInt();
// m = inputReader.readInt();
vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
// a[i][j] = inputReader.readInt();
}
}
// inputReader.close();
long long result = count_rectangles(a);
printf("%lld\n", result);
fclose(stdout);
return 0;
}
#endif
