#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX_N = 2500 + 1;
vector<int> row_conds[MAX_N][MAX_N];
vector<int> col_conds[MAX_N][MAX_N];
pii row_range[MAX_N][MAX_N]; // in the same row
pii col_range[MAX_N][MAX_N]; // in the same col
ll count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a[0].size();
memset(row_range, -1, sizeof row_range);
memset(col_range, -1, sizeof col_range);
for (int i=1; i+1<n; ++i) {
vector<pii> st;
for (int j=0; j<m; ++j) {
while (!st.empty() && st.back().first < a[i][j]) {
row_range[i][st.back().second].second = j-1;
st.pop_back();
}
st.push_back({ a[i][j], j });
}
st.clear();
for (int j=m-1; j>=0; --j) {
while (!st.empty() && st.back().first < a[i][j]) {
row_range[i][st.back().second].first = j+1;
st.pop_back();
}
st.push_back({ a[i][j], j });
}
}
for (int i=1; i+1<m; ++i) {
vector<pii> st;
for (int j=0; j<n; ++j) {
while (!st.empty() && st.back().first < a[j][i]) {
col_range[st.back().second][i].second = j-1;
st.pop_back();
}
st.push_back({ a[j][i], j });
}
st.clear();
for (int j=n-1; j>=0; --j) {
while (!st.empty() && st.back().first < a[j][i]) {
col_range[st.back().second][i].first = j+1;
st.pop_back();
}
st.push_back({ a[j][i], j });
}
}
for (int i=1; i+1<n; ++i) {
for (int j=1; j+1<m; ++j) {
auto[a, b] = row_range[i][j];
if (a != -1 && b != -1) row_conds[a][b].push_back(i);
}
}
for (int j=1; j+1<m; ++j) {
for (int i=1; i+1<n; ++i) {
auto[c, d] = col_range[i][j];
if (c != -1 && d != -1) col_conds[c][d].push_back(j);
}
}
for (int i=0; i<MAX_N; ++i) {
for (int j=i; j<MAX_N; ++j) {
row_conds[i][j].erase(unique(row_conds[i][j].begin(), row_conds[i][j].end()), row_conds[i][j].end());
col_conds[i][j].erase(unique(col_conds[i][j].begin(), col_conds[i][j].end()), col_conds[i][j].end());
}
}
ll ans = 0;
vector<ll> cands;
for (int j=1; j+1<m; ++j) {
for (int i=1; i+1<n; ++i) {
auto[a, b] = row_range[i][j];
auto[c, d] = col_range[i][j];
if (a != -1 && b != -1 && c != -1 && d != -1) cands.push_back((ll)n*m*(a*m+b)+(c*m+d));
}
}
sort(cands.begin(), cands.end());
cands.erase(unique(cands.begin(), cands.end()), cands.end());
for (ll x: cands) {
int a = x / (n*m);
int c = x % (n*m);
int b = a % m;
a = a / m;
int d = c % m;
c = c / m;
auto row_lb = lower_bound(row_conds[a][b].begin(), row_conds[a][b].end(), c);
auto row_ub = lower_bound(row_conds[a][b].begin(), row_conds[a][b].end(), d);
auto col_lb = lower_bound(col_conds[c][d].begin(), col_conds[c][d].end(), a);
auto col_ub = lower_bound(col_conds[c][d].begin(), col_conds[c][d].end(), b);
// cout << i << ' ' << j << ' ' << *row_lb << ' ' << *row_ub << ' ' << *col_lb << ' ' << *col_ub << endl;
if (*row_lb == c && *row_ub == d && row_ub-row_lb == d-c
&& *col_lb == a && *col_ub == b && col_ub-col_lb == b-a) ans++;
}
// for (int i=1; i+1<n; ++i) {
// for (int j=1; j+1<m; ++j) {
// auto[a, b] = row_range[i][j];
// auto[c, d] = col_range[i][j];
// if (a != -1 && b != -1 && c != -1 && d != -1) {
// }
// }
// }
return ans;
}
