#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int maxn = 2505, INF = (int)1e4;
int n, m;
short Y1[maxn][maxn], Y2[maxn][maxn], X1[maxn][maxn], X2[maxn][maxn];
vector<bool> jo;
struct adat{
int l, r, x, ind;
adat(){}
adat(int l, int r, int x, int ind) : l(l), r(r), x(x), ind(ind) {}
};
void calc_elott(vector<vector<int>> &a, function<bool(int, int)> comp){
for(int i = 0; i < n; i++){
Y1[i][0] = -1;
for(int j = 1; j < m; j++){
Y1[i][j] = j-1;
while(Y1[i][j] >= 0 && comp(a[i][Y1[i][j]], a[i][j]))
Y1[i][j] = Y1[i][Y1[i][j]];
}
Y2[i][m-1] = m;
for(int j = m-2; j >= 0; j--){
Y2[i][j] = j+1;
while(Y2[i][j] < m && comp(a[i][Y2[i][j]], a[i][j]))
Y2[i][j] = Y2[i][Y2[i][j]];
}
}
for(int i = 0; i < m; i++){
X1[0][i] = -1;
for(int j = 1; j < n; j++){
X1[j][i] = j-1;
while(X1[j][i] >= 0 && comp(a[X1[j][i]][i], a[j][i]))
X1[j][i] = X1[X1[j][i]][i];
}
X2[n-1][i] = n;
for(int j = n-2; j >= 0; j--){
X2[j][i] = j+1;
while(X2[j][i] < n && comp(a[X2[j][i]][i], a[j][i]))
X2[j][i] = X2[X2[j][i]][i];
}
}
}
vector<adat> U[maxn+1], D[maxn+1], L[maxn+1], R[maxn+1];
pair<int, int> sor[maxn+2];
void ell(short t[], vector<adat> &ints, int n, function<bool(int, int)> comp){
vector<vector<adat>> vh(n);
for(adat &d : ints)
vh[d.r].push_back(d);
int x = 0;
for(int i = 0; i < n; i++){
while(x > 0 && comp(t[i], sor[x-1].second))
x--;
sor[x++] = make_pair(i, t[i]);
for(adat &d : vh[i])
if(comp(lower_bound(sor, sor+x, make_pair(d.l, -INF))->second, d.x))
jo[d.ind] = false;
}
}
vector<pair<int, int>> sarok[maxn][maxn];
bool volt[maxn][maxn] = {};
long long count_rectangles(std::vector<std::vector<int>> a){
n = (int)a.size();
m = (int)a[0].size();
calc_elott(a, [](int a, int b){ return a <= b; });
int ind = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
int x1 = X1[i][j], x2 = X2[i][j], y1 = Y1[i][j], y2 = Y2[i][j];
if(x1 != -1 && y1 != -1 && x2 != n && y2 != m)
sarok[x1][y1].emplace_back(x2, y2);
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
for(pair<int, int> &p : sarok[i][j]){
int x1 = i, y1 = j, x2 = p.first, y2 = p.second;
if(volt[x2][y2]) continue;
volt[x2][y2] = true;
U[x1].emplace_back(y1+1, y2-1, x2, ind);
D[x2].emplace_back(y1+1, y2-1, x1, ind);
L[y1].emplace_back(x1+1, x2-1, y2, ind);
R[y2].emplace_back(x1+1, x2-1, y1, ind);
jo.push_back(true);
ind++;
}
for(pair<int, int> &p : sarok[i][j])
volt[p.first][p.second] = false;
}
}
calc_elott(a, [](int a, int b){ return a < b; });
for(int i = 0; i < maxn; i++){
for(int j = i+1; j < maxn; j++){
swap(Y1[i][j], Y1[j][i]);
swap(Y2[i][j], Y2[j][i]);
}
}
for(int i = 0; i < n; i++){
ell(X1[i], D[i], m, [](int a, int b){return a > b;});
ell(X2[i], U[i], m, [](int a, int b){return a < b;});
}
for(int i = 0; i < m; i++){
ell(Y1[i], R[i], n, [](int a, int b){return a > b;});
ell(Y2[i], L[i], n, [](int a, int b){return a < b;});
}
return accumulate(jo.begin(), jo.end(), 0);
}
