#include <bits/stdc++.h>
#define ll long long
#define all(lpv) lpv.begin(), lpv.end()
#define pot(x, y) lower_bound(x.begin(), x.end(), y) - x.begin() + 1
using namespace std;
//#define lpv
#ifndef lpv
#include "rect.h"
#endif // lpv
const int N = 3e3 + 5;
const int oo = 1e8;
int n, m, a[N][N], f[2][N << 1][N];
ll ans;
vector<int> col[N][N];
int get(int t,int l,int r,int x) {
r++;
int ret = oo;
for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2) {
if(l & 1) ret = min(ret, f[t][l ++][x]);
if(r & 1) ret = min(ret, f[t][-- r][x]);
}
return ret;
}
long long count_rectangles(std::vector<std::vector<int>> _a) {
n = _a.size();
m = _a[0].size();
for(int i = 1; i <= n; i ++) {
for(int j = 1; j <= m; j ++) a[i][j] = _a[i - 1][j - 1];
}
for(int i = 1; i <= n; i ++) {
stack<int> st;
st.push(0);
a[i][0] = oo;
for(int j = 1; j <= m; j ++) {
while(!st.empty() && a[i][st.top()] < a[i][j]) st.pop();
int x = (st.top() == 0 ? 1 : st.top());
f[0][i + n - 1][j] = j - x;
st.push(j);
}
while(!st.empty()) st.pop();
st.push(m + 1);
a[i][m + 1] = oo;
for(int j = m; j >= 1; j --) {
while(!st.empty() && a[i][st.top()] < a[i][j]) st.pop();
int x = (st.top() == m + 1 ? m : st.top());
// if(i == 3 && j == 1) cerr << x << " " << x - j << " " << << " g\n";
f[1][i + n - 1][j] = x - j;
st.push(j);
}
}
for(int j = 1; j <= m; j ++) {
for(int i = n - 1; i >= 1; i --) for(int t = 0; t <= 1; t ++) {
f[t][i][j] = min(f[t][i << 1][j], f[t][i << 1|1][j]);
}
}
for(int j = 2; j < m; j ++) {
stack<int> st;
st.push(0);
a[0][j] = oo;
for(int i = 1; i <= n; i ++) {
while(!st.empty() && a[st.top()][j] < a[i][j]) st.pop();
int x = st.top();
if(x && x != i - 1) col[i][x].push_back(j);
st.push(i);
}
while(!st.empty()) st.pop();
st.push(n + 1);
a[n + 1][j] = oo;
for(int i = n; i >= 1; i --) {
while(!st.empty() && a[st.top()][j] < a[i][j]) st.pop();
int x = st.top();
if(x != n + 1 && x != i + 1) {
col[x][i].push_back(j);
// if(j == 4) cerr << x << " " << i << " " << j << " o\n";
}
st.push(i);
}
}
for(int r = 1; r <= n; r ++) {
// if(r != 3) continue;
for(int l = r - 2; l >= 1; l --) if(!col[r][l].empty()) {
sort(all(col[r][l])); col[r][l].resize(unique(all(col[r][l])) - col[r][l].begin());
// cerr << r << " " << l << " t\n";
// for(auto j : col[r][l]) cerr << j << " ";
// cerr << "\n";
int pre = -1, last = -1;
for(auto i : col[r][l]) {
if(pre == -1) pre = i;
else if(i > last + 1) pre = i;
last = i;
int val = get(0, l + 1, r - 1, i + 1);
int pos = i + 1 - val;
// if(i == 4) cerr << l + 1 << " " << r - 1 << " " << i + 1 << " " << pos << " " << pre << " t\n";
if(pos >= pre - 1 && pos != i) {
int tmp = get(1, l + 1, r - 1, pos);
if(pos + tmp >= i + 1) {
ans++;
// cerr << pos << " " << i + 1 << " " << l + 1 << " " << r - 1 << " x1\n";
}
}
}
pre = -1, last = -1;
reverse(all(col[r][l]));
for(auto i : col[r][l]) {
if(pre == -1) pre = i;
else if(i < last - 1) pre = i;
last = i;
int val = get(1, l + 1, r - 1, i - 1);
int pos = i - 1 + val;
if(pos <= pre + 1 && pos != i) {
int tmp = get(0, l + 1, r - 1, pos);
if(pos - tmp < i - 1) {
ans++;
// cerr << i - 1 << " " << pos << " " << l + 1 << " " << r - 1 << " h\n";
}
}
}
// cerr << l << " " << ans << " g\n";
}
// cerr << r << " " << ans << " f\n";
}
cerr << ans << "\n";
return ans;
}
/*
6 6
2 13 15 14 12 15
17 6 8 3 10 2
6 18 16 20 13 12
4 4 4 20 19 13
5 12 12 2 10 17
9 9 3 17 9 19
6 5
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
*/
#ifdef lpv
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define task "v"
if(fopen(task ".inp","r")) {
freopen(task ".inp","r",stdin);
freopen(task ".out","w",stdout);
}
int _n, _m;cin >> _n >> _m;
vector<vector<int>> _a;
for(int i = 1; i <= _n; i ++) {
vector<int> tmp;
for(int j = 1; j <= _m; j ++) {
int x; cin >> x;
tmp.push_back(x);
}
_a.push_back(tmp);
}
cout << count_rectangles(_a);
}
#endif // lpv
