// Skyqwq
#include <bits/stdc++.h>

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

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }

template <typename T> void inline read(T &x) {
    int f = 1; x = 0; char s = getchar();
    while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
    while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
    x *= f;
}

const int N = 2505;

int n, m, a[N][N], f[N], mx[N], mn[N], w[N], now, ans;
bool vis[N][N];

PII e[N];

vector<int> R[N][N], s[N];

int la[N][N], cur[N][N];

PII d1[N], d2[N];

int t1, t2;

void inline init(int n) {
	for (int i = 1; i <= n; i++) f[i] = i, mx[i] = i, mn[i] = i;
}

int find(int x) {
	return x == f[x] ? x : f[x] = find(f[x]);
}

bool merge(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return 0;
	f[x] = y, chkMax(mx[y], mx[x]), chkMin(mn[y], mn[x]), chkMax(w[y], w[x]);
	return 1;
}

void inline chk(int x) {
	x = find(x);
	if (mn[x] > 1 && mx[x] < m && w[x] < a[now][mn[x] - 1] && w[x] < a[now][mx[x] + 1]) {
		R[now][mx[x]].pb(mx[x] - mn[x] + 1);
	}
}

struct BIT{
	int c[N];
	void inline add(int x, int k) {
		for (; x <= m; x += x & -x) c[x] += k;
	}
	void inline clr(int x) {
		for (; x <= m; x += x & -x) c[x] = 0;
	}
	int inline ask(int x) {
		int ret = 0;
		for (; x; x -= x & -x) ret += c[x];
		return ret;
	}
} to[N];

bool mg(int x, int y) {
	x = find(x), y = find(y);
	if (x == y) return 0;
	if (s[x].size() < s[y].size()) swap(x, y);
	f[x] = y, chkMax(mx[y], mx[x]), chkMin(mn[y], mn[x]), chkMax(w[y], w[x]);
	vector<int> ne;
	for (int v: s[y])
		if (vis[x][v]) ne.pb(v);
		else vis[y][v] = 0, to[y].add(v, -1);
	s[y] = ne;
	return 1;
}

void inline ck(int x) {
	x = find(x);
	if (mn[x] > 1 && mx[x] < n && w[x] < a[mn[x] - 1][now] && w[x] < a[mx[x] + 1][now]) {
		d2[++t2] = mp(mn[x], mx[x]);
		cur[mn[x]][mx[x]] = la[mn[x]][mx[x]] + 1;
		int o = cur[mn[x]][mx[x]];
		ans += to[x].ask(o);
	}
}

int main() {
	read(n), read(m);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			read(a[i][j]);
		}
	}
	for (int i = 1; i <= n; i++) {
		init(m);
		now = i;
		for (int j = 1; j <= m; j++) e[j] = mp(a[i][j], j), w[j] = a[i][j];
		for (int j = 2; j < m; j++) chk(j);
		sort(e + 1, e + 1 + m);
		for (int j = 1; j <= m; j++) {
			int x = e[j].se;
			if (x > 1 && a[i][x] >= a[i][x - 1]) {
				if (merge(x, x - 1)) chk(x);
			}
			if (x < m && a[i][x] >= a[i][x + 1])
				if (merge(x, x + 1)) chk(x);
		}
	}
	for (int i = 1; i <= m; i++) {
		now = i;
		init(n);
		for (int j = 1; j <= n; j++) {
			e[j] = mp(a[j][i], j), w[j] = a[j][i];
			for (int v: R[j][i]) {
				vis[j][v] = 1;
				s[j].pb(v);
				to[j].add(v, 1);
			}
		}
		for (int j = 2; j < n; j++) ck(j);
		sort(e + 1, e + 1 + n);
		for (int j = 1; j <= n; j++) {
			int x = e[j].se;
			if (x > 1 && a[x][i] >= a[x - 1][i]) {
				if (mg(x, x - 1)) ck(x);
			}
			if (x < n && a[x][i] >= a[x + 1][i])
				if (mg(x, x + 1)) ck(x);
		}
		for (int j = 1; j <= t1; j++) {
			int A = d1[j].fi, B = d1[j].se;
			la[A][B] = 0;
		}
		for (int j = 1; j <= t2; j++) {
			int A = d2[j].fi, B = d2[j].se;
			la[A][B] = cur[A][B];
			cur[A][B] = 0;
			d1[j] = d2[j];
		}
		for (int j = 1; j <= n; j++) {
			for (int v: R[j][i])
				vis[j][v] = 0, to[j].clr(v);
			s[j].clear();
		}
		t1 = t2;
		t2 = 0;
	}
	printf("%d\n", ans);
    return 0;
}

implementer.cpp:22:34: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   22 | inline void freadn(register int *Q) {
      |                                  ^
implementer.cpp:27:37: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   27 | inline void freadstr(register char *s) {
      |                                     ^
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/ccC1QDoI.o: in function `main':
answer.code:(.text.startup+0x0): multiple definition of `main'; /tmp/cczPBrIK.o:implementer.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cczPBrIK.o: in function `main':
implementer.cpp:(.text.startup+0x598): 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