#include "rect.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
#define endl "\n"
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const int N = 2510;
const int LOG = 20;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
vector < pii > R[N][N], D[N][N];
ll tot;
ll count_rectangles(vector < vector < int > > A)
{
int n = SZ(A), m = SZ(A[0]);
///printf("n = %d m = %d\n", n, m);
for(int i = 0; i < n; i ++)
{
vector < int > vec;
for(int j = 0; j < m; j ++)
{
while(SZ(vec) && A[i][j] > A[i][vec.back()])
{
if(j - vec.back() > 1) R[i][vec.back() + 1].push_back({j - 1, i});
vec.pop_back();
}
if(SZ(vec))
{
if(j - vec.back() > 1) R[i][vec.back() + 1].push_back({j - 1, i});
if(A[i][vec.back()] == A[i][j]) vec.pop_back();
}
vec.push_back(j);
}
}
for(int j = 0; j < m; j ++)
{
vector < int > vec;
for(int i = 0; i < n; i ++)
{
while(SZ(vec) && A[i][j] > A[vec.back()][j])
{
if(i - vec.back() > 1) D[vec.back() + 1][j].push_back({i - 1, j});
vec.pop_back();
}
if(SZ(vec))
{
if(i - vec.back() > 1) D[vec.back() + 1][j].push_back({i - 1, j});
if(A[i][j] == A[vec.back()][j]) vec.pop_back();
}
vec.push_back(i);
}
}
for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) { sort(all(R[i][j])), sort(all(D[i][j])); }
for(int i = n - 1; ~i; i --)
{
for(int j = m - 1; ~j; j --)
{
for(int t = 0; t < SZ(R[i][j]); t ++)
{
int id = lower_bound(all(R[i + 1][j]), R[i][j][t]) - R[i + 1][j].begin();
if(id < SZ(R[i + 1][j]) && R[i + 1][j][id].F == R[i][j][t].F)
{
R[i][j][t].S = R[i + 1][j][id].S;
}
}
for(int t = 0; t < SZ(D[i][j]); t ++)
{
int id = lower_bound(all(D[i][j + 1]), D[i][j][t]) - D[i][j + 1].begin();
if(id < SZ(D[i][j + 1]) && D[i][j + 1][id].F == D[i][j][t].F)
{
D[i][j][t].S = D[i][j + 1][id].S;
}
}
}
}
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
for(auto [a, b] : R[i][j])
{
for(auto [c, d] : D[i][j])
{
tot += (a <= d && c <= b);
}
}
}
}
return tot;
}
