#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
const int N = 2510;
int n,m;
vector<array<int, 2>> gdr[N][N];
vector<array<int, 2>> gdc[N][N];
struct Side {
int r1, r2, c1, c2;
};
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][j].push_back({stk.back(), 1});
}
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][stk.back()].push_back({j,1});
}
}
stk.push_back(j);
}
}
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[j][i].push_back({stk.back(),1});
}
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()) {
if(a[j][i] != a[stk.back()][i]) {
gdc[stk.back()][i].push_back({j, 1});
}
}
stk.push_back(j);
}
}
long long ans=0;
for(int i = 0;i<n;i++) {
for(int j = 0;j<m;j++) {
sort(gdr[i][j].begin(), gdr[i][j].end());
sort(gdc[i][j].begin(), gdc[i][j].end());
gdr[i][j].erase(unique(gdr[i][j].begin(), gdr[i][j].end()), gdr[i][j].end());
gdc[i][j].erase(unique(gdc[i][j].begin(), gdc[i][j].end()), gdc[i][j].end());
if(i) {
for(auto &[u, v]:gdr[i][j]) {
auto it = lower_bound(gdr[i-1][j].begin(), gdr[i-1][j].end(), array<int,2>{u, 0});
if(it!=gdr[i-1][j].end() and (*it)[0] == u) {
v+=(*it)[1];
}
}
}
if(j) {
for(auto &[u, v]:gdc[i][j]) {
auto it = lower_bound(gdc[i][j-1].begin(), gdc[i][j-1].end(), array<int,2>{u, 0});
if(it!=gdc[i][j-1].end() and (*it)[0] == u) {
v+=(*it)[1];
}
}
}
if(i and j) {
for(auto k:gdr[i-1][j]) {
if(k[0] +1 == j)continue;
for(auto k2:gdc[i][j-1]) {
if(k2[0] +1 == i)continue;
// cout << i << " " << j << " " << k[0] << " " << k2[0] << " " << k[1] << " " << k2[1] << endl;
if(k[0] >= j - k2[1]-1 and k2[0] >= i - k[1] - 1)ans++;
}
}
}
}
}
return ans;
}
