#include<bits/stdc++.h>
using namespace std;
const int N = 2500 + 5;
const int MX = 2;
struct SegTree {
int st[4 * N];
SegTree(int n) {
for (int i = 0; i < 4 * n; i++) st[i] = 0;
}
void update(int v, int tl, int tr, int idx, int add) {
if (tl == tr) {
st[v] += add;
return;
}
int mid = tl + (tr - tl) / 2;
if (idx <= mid) update(2 * v, tl, mid, idx, add);
else update(2 * v + 1, mid + 1, tr, idx, add);
st[v] = st[2 * v] + st[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r) {
if (l > r) return 0;
if (tl == l && tr == r) return st[v];
int mid = tl + (tr - tl) / 2;
return query(2 * v, tl, mid, l, min(mid, r)) + query(2 * v + 1, mid + 1, tr, max(mid + 1, l), r);
}
};
vector<pair<int,int>> sorted[MX];
set<int> col[N];
int row_order[N][N];
int row_order_cnt[N];
vector<int> col_has[N][N];
bool has[N][N];
pair<int,int> dp_row[N][N];
int dp_row_cnt[N];
int row_has[N][N];
int row_cnt[N];
long long int count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) sorted[a[i][j]].push_back({i, j});
}
for (int i = 0; i < N; i++) {
col[i].insert(-1);
col[i].insert(n);
}
for (int i = 0; i < N; i++) row_order_cnt[i] = 0;
for (int i = MX - 1; i >= 0; i--) {
for (auto [x, y]: sorted[i]) {
row_order[x][row_order_cnt[x]++] = y;
col[y].insert(x);
}
for (auto [x, y]: sorted[i]) {
auto it = col[y].find(x);
it--;
if (*it != -1 && *it < x - 1) {
int l = (*it) + 1;
int r = x - 1;
if (col_has[l][y].empty() || col_has[l][y].back() > r) col_has[l][y].push_back(r);
}
it++;
it++;
if (*it != n && *it > x + 1) {
int l = x + 1;
int r = (*it) - 1;
if (col_has[l][y].empty() || col_has[l][y].back() > r) col_has[l][y].push_back(r);
}
}
}
long long int ans = 0;
SegTree st(m);
for (int i = 0; i < m; i++) for (int j = 0; j < m; j++) has[i][j] = false;
for (int i = 0; i < m; i++) row_cnt[i] = dp_row_cnt[i] = 0;
for (int i = n - 2; i > 0; i--) {
set<int> row;
row.insert(-1);
row.insert(m);
int p = 0;
while (p < m) {
int curr = a[i][row_order[i][p]];
int start = p;
while (p < m && a[i][row_order[i][p]] == curr) {
row.insert(row_order[i][p++]);
}
for (int j = start; j < p; j++) {
int y = row_order[i][j];
auto it = row.find(y);
it--;
if (*it != -1 && *it < y - 1) {
int l = (*it) + 1;
int r = y - 1;
row_has[l][row_cnt[l]++] = r;
has[l][r] = true;
}
it++;
it++;
if (*it != m && *it > y + 1) {
int l = y + 1;
int r = (*it) - 1;
row_has[l][row_cnt[l]++] = r;
has[l][r] = true;
}
}
}
vector<pair<int,int>> dp_col;
for (int j = m - 2; j > 0; j--) {
vector<pair<int,int>> ndp_col;
int p1 = 0, p2 = 0;
while (p1 < col_has[i][j].size() || p2 < dp_col.size()) {
if (p1 == col_has[i][j].size()) p2++;
else if (p2 == dp_col.size()) ndp_col.emplace_back(col_has[i][j][p1++], j);
else if (col_has[i][j][p1] > dp_col[p2].first) ndp_col.emplace_back(col_has[i][j][p1++], j);
else if (col_has[i][j][p1] < dp_col[p2].first) p2++;
else {
p1++;
ndp_col.push_back(dp_col[p2++]);
}
}
dp_col = move(ndp_col);
vector<pair<int,int>> ndp_row;
for (int id = 0; id < dp_row_cnt[j]; id++) {
auto [x, y] = dp_row[j][id];
if (!has[j][y]) continue;
has[j][y] = false;
ndp_row.emplace_back(x, y);
}
for (int x = 0; x < row_cnt[j]; x++) {
int y = row_has[j][x];
if (!has[j][y]) continue;
has[j][y] = false;
ndp_row.emplace_back(i, y);
}
dp_row_cnt[j] = ndp_row.size();
for (int id = 0; id < ndp_row.size(); id++) dp_row[j][id] = ndp_row[id];
row_cnt[j] = 0;
int ptr = 0;
for (auto [x, y]: dp_col) {
while (ptr < dp_row_cnt[j] && dp_row[j][ptr].first >= x) {
st.update(1, 0, m - 1, dp_row[j][ptr++].second, 1);
}
ans += st.query(1, 0, m - 1, j, y);
}
while (--ptr >= 0) st.update(1, 0, m - 1, dp_row[j][ptr].second, -1);
}
}
return ans;
}
