//#define local
#ifndef local
#include "rect.h"
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ll long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<ll, ll> ii;
typedef pair<ii, ll> iii;
typedef pair<ii, ii> iiii;

const ll N = 2505 + 5;

const ll oo = 1e18 + 7, mod = 1e9 + 7;

mt19937 rng(1);

ll rnd(ll l, ll r){
	ll temp = rng() % (r - l + 1);
	return abs(temp) + l;
}

ll n, m, a[N][N];

ll mxr[N][N], mxl[N][N], mxd[N][N], mxu[N][N];

vector<ii> vc;

vector<ll> events[N];

ll minr[N], maxl[N];

ll bit[N];

void upd(ll id, ll val){
	for(; id <= m; id += id & -id) bit[id] += val;
}

ll get(ll id){
	ll ans = 0;
	for(; id; id -= id & -id) ans += bit[id];
	return ans;
}

ll count_rectangles(vector<vector<int>> arr){
	n = arr.size(), m = arr[0].size();
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < m; j++) a[i][j] = arr[i][j];
	}
	for(ll i = 0; i < n; i++){
		stack<ll> stk;
		stk.push(-1);
		for(ll j = 0; j < m; j++){
			while(stk.top() >= 0 && a[i][stk.top()] < a[i][j]) stk.pop();
			mxl[i][j] = stk.top() + 1;
			stk.push(j);
		}
	}
	for(ll i = 0; i < n; i++){
		stack<ll> stk;
		stk.push(-1);
		for(ll j = 0; j < m; j++){
			while(stk.top() >= 0 && a[i][stk.top()] < a[i][j]) stk.pop();
			mxl[i][j] = stk.top() + 1;
			stk.push(j);
		}
	}
	for(ll i = 0; i < n; i++){
		stack<ll> stk;
		stk.push(m);
		for(ll j = m - 1; j >= 0; j--){
			while(stk.top() < m && a[i][stk.top()] < a[i][j]) stk.pop();
			mxr[i][j] = stk.top() - 1;
			stk.push(j);
		}
	}
	for(ll i = 0; i < m; i++){
		stack<ll> stk;
		stk.push(-1);
		for(ll j = 0; j < n; j++){
			while(stk.top() >= 0 && a[stk.top()][i] < a[j][i]) stk.pop();
			mxu[j][i] = stk.top() + 1;
			stk.push(j);
		}
	}
	for(ll i = 0; i < m; i++){
		stack<ll> stk;
		stk.push(n);
		for(ll j = n - 1; j >= 0; j--){
			while(stk.top() < n && a[stk.top()][i] < a[j][i]) stk.pop();
			mxd[j][i] = stk.top() - 1;
			stk.push(j);
		}
	}
	for(ll i = 0; i < n; i++){
		//for(ll j = 0; j < m; j++) cout << i << " " << j << " " << mxr[i][j] << " " << mxl[i][j] << " " << mxu[i][j] << " " << mxd[i][j] << "\n";
	}
	ll answer = 0;
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < m; j++){
			minr[j] = oo, maxl[j] = -oo;
		}
		for(ll j = i + 2; j < n; j++){
			for(ll k = 0; k < m; k++){
				minr[k] = min(minr[k], mxr[j - 1][k]);
				maxl[k] = max(maxl[k], mxl[j - 1][k]);
			}
			vc.clear();
			ll lst = -oo;
			for(ll k = 1; k < m; k++){
				if(mxd[i][k] >= j - 1 && mxu[j][k] <= i + 1 && k < (m - 1)){
					if(lst == -oo) lst = k;
				}
				else{
					if(lst >= 0) vc.pb({lst, k - 1});
					lst = -oo;
				}
			}
			for(ll k = 0; k <= m; k++){
				events[k].clear();
				bit[k] = 0;
			}
			for(auto it : vc){
				//cout << i << " " << j << " " << it.fi << " " << it.se << "\n";
				//cout << minr[it.fi - 1] << " " << maxl[it.fi + 1] << "\n";
				//for(ll k = it.fi - 1; k < it.se; k++) events[min(it.se, minr[k]) + 1];
				for(ll k = it.fi; k <= it.se; k++){
					upd(k, 1);
					events[min(it.se, minr[k - 1]) + 1].pb(k);
					for(auto it : events[k]) upd(it, -1);
					//cout << maxl[k + 1] << " " << 
					answer += get(m) - get(max(it.fi, maxl[k + 1] - 1));
					//cout << min(it.se, minr[k - 1]) + 1 << " " << maxl[k + 1] << "\n";
				}
				//cout << answer << "\n";
			}
		}
	}
	return answer;
}

#ifdef local
void process(){
	ll n, m;
	cin >> n >> m;
	vector<vector<int>> board;
	board.resize(n);
	for(ll i = 0; i < n; i++) board[i].resize(m);
	for(ll i = 0; i < n; i++){
		for(ll j = 0; j < m; j++) cin >> board[i][j];
	}
	cout << count_rectangles(board) << "\n";
}

signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("kek.inp", "r", stdin);
	freopen("kek.out", "w", stdout);
	process();
}
#endif