#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define X first
#define Y second
#define all(x) (x).begin(), (x).end()
#define SZ(x) int((x).size())
#define sep ' '
const int MAXN = 2510;
const int MOD = 1e9 + 7;
int n , m;
vector<pii> R[MAXN][MAXN] , D[MAXN][MAXN];
ll count_rectangles(vector<vector<int>> A) {
n = SZ(A); m = SZ(A[0]);
for(int i = 0 ; i < n ; i++){
vector<int> stk;
for(int j = 0 ; j < m ; j++){
int flag = 1;
while(SZ(stk) && A[i][j] >= A[i][stk.back()]){
if(A[i][j] == A[i][stk.back()]) flag = 0;
if(j - stk.back() > 1){
R[i][stk.back() + 1].push_back({j - 1 , i});
}
stk.pop_back();
}
if(flag && SZ(stk) && j - stk.back() > 1){
R[i][stk.back() + 1].push_back({j - 1 , i});
}
stk.push_back(j);
}
}
for(int i = 0 ; i < m ; i++){
vector<int> stk;
for(int j = 0 ; j < n ; j++){
int flag = 1;
while(SZ(stk) && A[j][i] >= A[stk.back()][i]){
if(A[j][i] == A[stk.back()][i]) flag = 0;
if(j - stk.back() > 1){
D[stk.back() + 1][i].push_back({j - 1 , i});
}
stk.pop_back();
}
if(flag && SZ(stk) && j - stk.back() > 1){
D[stk.back() + 1][i].push_back({j - 1 , i});
}
stk.push_back(j);
}
}
for(int i = n - 1 ; i >= 0 ; i--){
for(int j = m - 1 ; j >= 0 ; j--){
sort(all(R[i][j]));
sort(all(D[i][j]));
for(int k = 0 ; k < SZ(R[i][j]) ; k++){
int ind = lower_bound(all(R[i + 1][j]) , R[i][j][k]) - R[i + 1][j].begin();
if(ind == SZ(R[i + 1][j]) || R[i + 1][j][ind].X != R[i][j][k].X) continue;
R[i][j][k] = R[i + 1][j][ind];
}
for(int k = 0 ; k < SZ(D[i][j]) ; k++){
int ind = lower_bound(all(D[i][j + 1]) , D[i][j][k]) - D[i][j + 1].begin();
if(ind == SZ(D[i][j + 1]) || D[i][j + 1][ind].X != D[i][j][k].X) continue;
D[i][j][k] = D[i][j + 1][ind];
}
}
}
ll ans = 0;
for(int i = 1 ; i + 1 < n ; i++){
for(int j = 1 ; j + 1 < m ; j++){
for(pii k : R[i][j]){
for(pii l : D[i][j]){
if(k.X <= l.Y && l.X <= k.Y){
ans++;
}
}
}
}
}
return ans;
}
