#include "rect.h"
#include <cstdio>
#include <unistd.h>
#include <cassert>
#include <string>
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=2500+10;
const double eps=1e-5;
const int mo=1e9+7;
int n,m;
int a[N][N];
int s[N],tail;
int l[N],r[N],pre[N];
vector<int> e[N][N],e2[N][N],e3[N][N];
int far_up[2][N][N],far_left[N][N];
int before[N];
int nxt[N];
ll res;
long long count_rectangles(std::vector<std::vector<int> > aa) {
n=aa.size(),m=aa[0].size();
FOR(i,n) FOR(j,m) a[i][j]=aa[i-1][j-1];
FOR(i,n) {
FOR(j,m) l[j]=r[j]=pre[j]=0;
tail=0;
FOR(j,m) {
while (tail>=1&&a[i][s[tail]]<=a[i][j]) tail--;
if (tail>=1) l[j]=s[tail]+1;
s[++tail]=j;
}
tail=0;
for (int j=m;j>=1;j--) {
while (tail>=1&&a[i][s[tail]]<a[i][j]) tail--;
if (tail>=1) {
if (a[i][j]==a[i][s[tail]]) {
if (pre[tail]) r[j]=pre[tail]-1;
} else {
r[j]=s[tail]-1;
}
}
s[++tail]=j;
if (tail==1) pre[tail]=0;
else if (a[i][j]!=a[i][s[tail-1]]) pre[tail]=s[tail-1];
else pre[tail]=pre[tail-1];
}
FOR(j,m) if (l[j]&&r[j]) {
e[i][l[j]].pb(r[j]);
//printf("(%d,%d) (%d,%d)\n",i,l[j],i,r[j]);
e3[i][r[j]].pb(l[j]);
}
}
FOR(j,m) {
FOR(i,n) l[i]=r[i]=pre[i]=0;
tail=0;
FOR(i,n) {
while (tail>=1&&a[s[tail]][j]<=a[i][j]) tail--;
if (tail>=1) l[i]=s[tail]+1;
s[++tail]=i;
}
tail=0;
for (int i=n;i>=1;i--) {
while (tail>=1&&a[s[tail]][j]<a[i][j]) tail--;
if (tail>=1) {
if (a[i][j]==a[s[tail]][j]) {
if (pre[tail]) r[i]=pre[tail]-1;
} else {
r[i]=s[tail]-1;
}
}
s[++tail]=i;
if (tail==1) pre[tail]=0;
else if (a[i][j]!=a[s[tail-1]][j]) pre[tail]=s[tail-1];
else pre[tail]=pre[tail-1];
}
FOR(i,n) if (l[i]&&r[i]) {
e2[r[i]][j].pb(l[i]);
//printf("(%d,%d) (%d,%d)\n",r[i],j,l[i],j);
}
}
int head;
FOR(i,n) {
FOR(j,m) {
for (int k=0;k<int(e[i][j].size());k++) {
far_up[i%2][j][e[i][j][k]]=far_up[(i-1)%2][j][e[i][j][k]]+1;
}
}
FOR(j,m) {
for (int k=0;k<int(e2[i][j].size());k++) {
far_left[e2[i][j][k]][j]=far_left[e2[i][j][k]][j-1]+1;
}
}
FOR(j,m) {
/*
head=e2[i][j].size()-1;
for (int u=e2[i][j].size()-1;u>=0;u--) {
before[u]=u+1;
nxt[u]=u-1;
}
for (int k=e3[i][j].size()-1;k>=0;k--) {
for (int u=head;u>=0;u=nxt[u]) {
if (far_up[i%2][e3[i][j][k]][j]<i-e2[i][j][u]+1) break;
if (far_left[e2[i][j][u]][j]>=j-e3[i][j][k]+1) {
res++;
} else {
if (before[u]!=e2[i][j].size()) nxt[before[u]]=nxt[u];
if (nxt[u]>=0) before[nxt[u]]=before[u];
if (u==head) head=nxt[u];
}
}
}*/
for (int k=int(e3[i][j].size())-1;k>=0;k--) {
for (int u=int(e2[i][j].size())-1;u>=0;u--) {
if (far_up[i%2][e3[i][j][k]][j]>=i-e2[i][j][u]+1&&far_left[e2[i][j][u]][j]>=j-e3[i][j][k]+1) {
res++;
}
}
}
}
FOR(j,m) {
for (int k=0;k<int(e[i-1][j].size());k++) {
far_up[(i-1)%2][j][e[i-1][j][k]]=0;
}
}
FOR(j,m) {
for (int k=0;k<int(e2[i][j].size());k++) {
far_left[e2[i][j][k]][j]=0;
}
}
}
return res;
}
#ifdef DEBUG
class InputReader {
private:
static const int SIZE = 4096;
int inputFileDescriptor;
char buf[SIZE];
int curChar;
int numChars;
public:
inline InputReader(int _inputFileDescriptor):
inputFileDescriptor(_inputFileDescriptor),
curChar(0),
numChars(0) {
}
inline void close() {
::close(inputFileDescriptor);
}
inline char read() {
assert(numChars != -1);
if (curChar >= numChars) {
curChar = 0;
numChars = ::read(inputFileDescriptor, buf, SIZE);
if (numChars == -1)
return -1;
}
return buf[curChar++];
}
inline int readInt() {
int c = eatWhite();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
assert(c >= '0' && c <= '9');
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
inline string readString() {
char c = eatWhite();
string res;
do {
res += c;
c = read();
} while (!isSpaceChar(c));
return res;
}
inline string readLine() {
string res;
while (true) {
char c = read();
if (c == '\n' || c == '\r' || c == -1)
break;
res += c;
}
return res;
}
inline char eatWhite() {
char c = read();
while (isSpaceChar(c))
c = read();
return c;
}
static inline bool isSpaceChar(char c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
};
int main() {
InputReader inputReader(STDIN_FILENO);
int 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++) {
a[i][j] = inputReader.readInt();
}
}
inputReader.close();
long long result = count_rectangles(a);
printf("%lld\n", result);
fclose(stdout);
return 0;
}
#endif
