//#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 int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair

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

const int N = 2505 + 5;

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

mt19937 rng(1);

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

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

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

vector<ii> vc;

vector<int> events[N];

int minr[N], maxl[N];

int bit[N];

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

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

int count_rectangles(vector<vector<int>> arr){
	n = arr.size(), m = arr[0].size();
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++) a[i][j] = arr[i][j];
	}
	for(int i = 0; i < n; i++){
		stack<int> stk;
		stk.push(-1);
		for(int 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(int i = 0; i < n; i++){
		stack<int> stk;
		stk.push(-1);
		for(int 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(int i = 0; i < n; i++){
		stack<int> stk;
		stk.push(m);
		for(int 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(int i = 0; i < m; i++){
		stack<int> stk;
		stk.push(-1);
		for(int 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(int i = 0; i < m; i++){
		stack<int> stk;
		stk.push(n);
		for(int 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(int i = 0; i < n; i++){
		//for(int j = 0; j < m; j++) cout << i << " " << j << " " << mxr[i][j] << " " << mxl[i][j] << " " << mxu[i][j] << " " << mxd[i][j] << "\n";
	}
	int answer = 0;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			minr[j] = oo, maxl[j] = -oo;
		}
		for(int j = i + 2; j < n; j++){
			for(int 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();
			int lst = -oo;
			for(int 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(int 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(int k = it.fi - 1; k < it.se; k++) events[min(it.se, minr[k]) + 1];
				for(int 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(0LL, 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(){
	int n, m;
	cin >> n >> m;
	vector<vector<int>> board;
	board.resize(n);
	for(int i = 0; i < n; i++) board[i].resize(m);
	for(int i = 0; i < n; i++){
		for(int 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

implementer.cpp: In function ‘void readinp()’:
implementer.cpp:19:14: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   19 |         fread(ptr, 0x1, inSize, stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccHB6MHB.o: in function `main':
implementer.cpp:(.text.startup+0x40c): undefined reference to `count_rectangles(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >)'
collect2: error: ld returned 1 exit status