#include <bits/stdc++.h>
using namespace std;
#include <bits/extc++.h>
template <class T, class Comp = less<T>>
using ordered_set = __gnu_pbds::tree<
T, __gnu_pbds::null_type, Comp,
__gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update
>;
const int N = 2500;
vector<int> where_h[N][N], where_v[N][N];
vector<int> jump_h[N][N], jump_v[N][N];
bool check(vector<int> &s, int a, int b) {
return (int) (upper_bound(s.begin(), s.end(), b) - lower_bound(s.begin(), s.end(), a)) == b - a + 1;
}
long long count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
for (int i = 0; i < n; ++i) {
vector<int> mono;
for (int j = 0; j < m; ++j) {
bool equal = false;
while (!mono.empty() && a[i][mono.back()] <= a[i][j]) {
equal = a[i][mono.back()] == a[i][j];
jump_h[i][mono.back() + 1].push_back(j - 1);
where_h[mono.back() + 1][j - 1].push_back(i);
mono.pop_back();
}
if (!mono.empty() && !equal) {
jump_h[i][mono.back() + 1].push_back(j - 1);
where_h[mono.back() + 1][j - 1].push_back(i);
}
mono.push_back(j);
}
}
for (int i = 0; i < m; ++i) {
vector<int> mono;
for (int j = 0; j < n; ++j) {
bool equal = false;
while (!mono.empty() && a[mono.back()][i] <= a[j][i]) {
equal = a[mono.back()][i] == a[j][i];
jump_v[mono.back() + 1][i].push_back(j - 1);
where_v[mono.back() + 1][j - 1].push_back(i);
mono.pop_back();
}
if (!mono.empty() && !equal) {
jump_v[mono.back() + 1][i].push_back(j - 1);
where_v[mono.back() + 1][j - 1].push_back(i);
}
mono.push_back(j);
}
}
int ans = 0;
for (int i1 = 0; i1 < n; ++i1) {
for (int j1 = 0; j1 < m; ++j1) {
for (auto i2 : jump_v[i1][j1]) {
for (auto j2 : jump_h[i1][j1]) {
if (i1 <= i2 && j1 <= j2) {
ans += check(where_v[i1][i2], j1, j2) && check(where_h[j1][j2], i1, i2);
}
}
}
}
}
return ans;
}
