#include <bits/stdc++.h>
using namespace std;
#include "rect.h"
//#define HOME
using ll = long long;
#define pb push_back
#define dbg(x) cerr << #x << " " << x<< "\n"
const int N = 2500;
int prvX[N][N], prvY[N][N], nxtX[N][N], nxtY[N][N];
inline bool check (int x1, int y1, int x2, int y2, int n, int m) {
if (x1 > 0 && y1 > 0 && x2 < n - 1 && y2 < m - 1) {
for (int i = x1; i <= x2; i++) {
for (int j = y1; j <= y2; j++) {
if (prvX[i][j] < y1 - 1) return false;
if (prvY[i][j] < x1 - 1) return false;
if (nxtX[i][j] > y2 + 1) return false;
if (nxtY[i][j] > x2 + 1) return false;
}
}
return true;
}
return false;
}
ll count_rectangles (vector <vector <int>> a) {
int n = a.size ();
int m = a[0].size ();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
prvX[i][j] = j - 1;
while (prvX[i][j] >= 0 && a[i][prvX[i][j]] <= a[i][j])
prvX[i][j] = prvX[i][prvX[i][j]];
}
for (int j = m - 1; j >= 0; j--) {
nxtX[i][j] = j + 1;
while (nxtX[i][j] < m && a[i][nxtX[i][j]] <= a[i][j])
nxtX[i][j] = nxtX[i][nxtX[i][j]];
}
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
prvY[i][j] = i - 1;
while (prvY[i][j] >= 0 && a[prvY[i][j]][j] <= a[i][j])
prvY[i][j] = prvY[prvY[i][j]][j];
}
for (int i = n - 1; i >= 0; i--) {
nxtY[i][j] = i + 1;
while (nxtY[i][j] < n && a[nxtY[i][j]][j] <= a[i][j])
nxtY[i][j] = nxtY[nxtY[i][j]][j];
}
}
set <pair <pair <int, int>, pair <int, int>>> ans;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (check (prvY[i][j] + 1, prvX[i][j] + 1, nxtY[i][j] - 1, nxtX[i][j] - 1, n, m))
ans.insert ({{prvY[i][j] + 1, prvX[i][j] + 1}, {nxtY[i][j] - 1, nxtX[i][j] - 1}});
return (int) ans.size ();
}
#ifdef HOME
int main() {
int n, m;
cin >> n >> m;
vector <vector <int>> a (n, vector <int> (m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
cout << count_rectangles (a) << "\n";
return 0;
}
#endif
/**
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
**/
