#include "rect.h"
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using ll = long long;
using namespace std;
const int n_ = 2501;
using P = pair<int, int>;
ll n, m, k, tc = 1, a, b, c, d, sum, x, y, z, base, ans, q;
short R[n_][n_], U[n_][n_], D[n_][n_], L[n_][n_];
vector<short>row[n_][n_];
vector<int>idx[n_][n_];
short tree_[n_];
short f(short l, short r) {
r++;
short ret = 0;
for (; l; l -= (l & -l))ret -= tree_[l];
for (; r; r -= (r & -r))ret += tree_[r];
return ret;
}
void update(short i, short val) {
i++;
for (; i <= max(n, m); i += i & -i)tree_[i] += val;
}
int get(short x, short y) {
return x * n_+ y;
}
long long count_rectangles(std::vector<std::vector<int> > arr) {
ll ret = 0;
n = arr.size();
m = arr[0].size();
for (int i = 0; i < n; i++) {
stack<P>A, B;
A.push({ arr[i][0],0 });
B.push({ arr[i][m - 1],m - 1 });
for (int j = 1; j < m; j++) {
while (A.size() && A.top().first <= arr[i][j])A.pop();
if (A.empty())L[i][j] = -1;
else L[i][j] = A.top().second;
A.push({ arr[i][j],j });
while (B.size() && B.top().first <= arr[i][m - 1 - j])B.pop();
if (B.empty())R[i][m - 1 - j] = -1;
else R[i][m - 1 - j] = B.top().second;
B.push({ arr[i][m - 1 - j],m - 1 - j });
}
}
for (int i = 0; i < m; i++) {
stack<P>A, B;
A.push({ arr[0][i],0 });
B.push({ arr[n - 1][i],n - 1 });
for (int j = 1; j < n; j++) {
while (A.size() && A.top().first <= arr[j][i])A.pop();
if (A.empty())U[j][i] = -1;
else U[j][i] = A.top().second;
A.push({ arr[j][i],j });
while (B.size() && B.top().first <= arr[n - 1 - j][i])B.pop();
if (B.empty())D[n - 1 - j][i] = -1;
else D[n - 1 - j][i] = B.top().second;
B.push({ arr[n - 1 - j][i],n - 1 - j });
}
}
vector<P>query;
for (int j = 1; j + 1 < m; j++)
for (int i = 1; i + 1 < n; i++) {
if (D[i][j] == -1 || U[i][j] == -1)continue;
if (row[U[i][j]][D[i][j]].size() && row[U[i][j]][D[i][j]].back() == j)continue;
row[U[i][j]][D[i][j]].push_back(j);
if (L[i][j] != -1 && R[i][j] != -1) {
query.push_back({get(L[i][j],R[i][j]),get(U[i][j],D[i][j]) });
}
}
sort(all(query));
query.erase(unique(query.begin(), query.end()), query.end());
int cnt = 0;
for (auto nxt : query) {
idx[nxt.second/n_][nxt.second%n_].push_back(cnt);
cnt++;
}
assert(cnt <= n * m);
vector<int>now(cnt + 1);
for (int i = 0; i < n; i++)
for (int j = i + 2; j < n; j++) {
for (auto nxt : row[i][j])update(nxt, 1);
for (auto nxt : idx[i][j]) {
ll l = query[nxt].first/n_, r = query[nxt].first%n_;
int len = f(l + 1, r - 1);
if (len == r - l - 1)now[nxt]++;
}
for (auto nxt : row[i][j])update(nxt, -1);
row[i][j].clear();
idx[i][j].clear();
}
cnt = 0;
for (auto nxt : query) {
if (now[cnt] == 0) {
cnt++;
continue;
}
idx[nxt.first / n_][nxt.first % n_].push_back(cnt);
cnt++;
}
for (int i = 1; i + 1 < n; i++)
for (int j = 1; j + 1 < m; j++) {
if (L[i][j] == -1 || R[i][j] == -1)continue;
if (row[L[i][j]][R[i][j]].size() && row[L[i][j]][R[i][j]].back() == i)continue;
row[L[i][j]][R[i][j]].push_back(i);
}
for (int i = 0; i < m; i++)
for (int j = i + 2; j < m; j++) {
for (auto nxt : row[i][j])update(nxt, 1);
for (auto nxt : idx[i][j]) {
ll l = query[nxt].second/n_, r = query[nxt].second%n_;
int len = f(l + 1, r - 1);
if (len == r - l - 1)ret++;
}
for (auto nxt : row[i][j])update(nxt, -1);
}
return ret;
}
