#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
const int N = 2510;
int n,m;
vector<pair<int,int>> gdr[N];
vector<pair<int,int>> gdc[N];
struct Side {
int r1, r2, c1, c2;
};
vector<pair<int,int>> hsides[N][N];
vector<pair<int,int>> vsides[N][N];
int fen[N];
void upd(int at, int add) {
at++;
while(at) {
fen[at]+=add;
at-=at&(-at);
}
}
int qry(int at) {
at++;
int sum=0;
while(at<N) {
sum+=fen[at];
at+=at&(-at);
}
return sum;
}
vector<int> stk;
long long count_rectangles(std::vector<std::vector<int> > a) {
n = a.size();
m = a[0].size();
for(int i = 0;i<n;i++) {
stk.clear();
for(int j = 0;j<m;j++) {
while(stk.size() and a[i][stk.back()] < a[i][j]){
stk.pop_back();
}
if(stk.size()) {
gdr[i].push_back({stk.back(), j});
}
stk.push_back(j);
}
stk.clear();
for(int j = m-1;j>=0;j--) {
while(stk.size() and a[i][stk.back()] < a[i][j])stk.pop_back();
if(stk.size()) {
if(a[i][j] != a[i][stk.back()])
gdr[i].push_back({j, stk.back()});
}
stk.push_back(j);
}
sort(gdr[i].begin(), gdr[i].end());
}
for(int i = 0;i<m;i++) {
stk.clear();
for(int j = 0;j<n;j++) {
while(stk.size() and a[stk.back()][i] < a[j][i]){
stk.pop_back();
}
if(stk.size()) {
gdc[i].push_back({stk.back(), j});
}
stk.push_back(j);
}
stk.clear();
for(int j = n-1;j>=0;j--) {
while(stk.size() and a[stk.back()][i] < a[j][i])stk.pop_back();
if(stk.size()) {
gdc[i].push_back({j, stk.back()});
}
stk.push_back(j);
}
sort(gdc[i].begin(), gdc[i].end());
gdc[i].erase(unique(gdc[i].begin(), gdc[i].end()), gdc[i].end());
}
Side seg;
for(int i = 0;i<n;i++) {
for(auto &pr:gdr[i]) {
if(pr.first +1 == pr.second)continue;
if(i!=n-1 and (*lower_bound(gdr[i+1].begin(), gdr[i+1].end(), pr)) == pr)continue;
seg.r1 = pr.first;
seg.r2 = pr.second;
seg.c2 = i;
for(int j = i;j>=0;j--){
auto it = (lower_bound(gdr[j].begin(), gdr[j].end(), pr));
if(it == gdr[j].end())break;
if((*it)!=pr)break;
seg.c1=j;
}
seg.c1--;
seg.c2++;
seg.c1=max(seg.c1, 0);
seg.c2=min(seg.c2, n-1);
for(int j = seg.c1;j<=seg.c2;j++) {
hsides[j][seg.r2].push_back(pair<int,int>(seg.c1, seg.r1));
}
}
}
// for(int i = 0;i<n;i++) {
// gdr[i].clear();
// }
for(int i = 0;i<m;i++) {
for(auto &pr:gdc[i]) {
if(pr.first +1 == pr.second)continue;
if(i!=m-1 and (*lower_bound(gdc[i+1].begin(), gdc[i+1].end(), pr)) == pr)continue;
seg.r1 = pr.first;
seg.r2 = pr.second;
seg.c2 = i;
for(int j = i;j>=0;j--){
auto it = (lower_bound(gdc[j].begin(), gdc[j].end(), pr));
if(it == gdc[j].end())break;
if((*it)!=pr)break;
seg.c1=j;
}
seg.c1--;
seg.c2++;
seg.c1=max(seg.c1, 0);
seg.c2=min(seg.c2, m-1);
for(int j = seg.c1;j<=seg.c2;j++) {
vsides[seg.r2][j].push_back(pair<int,int>(seg.r1, seg.c1));
}
}
}
long long ans=0;
for(int i = 0;i<n;i++) {
for(int j = 0;j<m;j++) {
int tmp=0;
sort(vsides[i][j].begin(), vsides[i][j].end());
sort(hsides[i][j].begin(), hsides[i][j].end());
int p1 = 0;
for(auto &k:vsides[i][j]) {
while(p1 < (int)hsides[i][j].size() and hsides[i][j][p1].first <= k.first) {
upd(hsides[i][j][p1++].second, 1);
}
ans+=qry(k.second);
}
while(p1 < (int)hsides[i][j].size()) {
upd(hsides[i][j][p1++].second, 1);
}
for(auto k:hsides[i][j]) {
upd(k.second, -1);
}
}
}
return ans;
}
