#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define SZ(x) int((x).size())
#define sep ' '
const int MAXN = 2510;
const int MOD = 1e9 + 7;
int n , m , L[MAXN][MAXN] , R[MAXN][MAXN];
vector<int> vec[MAXN][MAXN];
int solve(int x , int y , int l , int r){
vector<pii> ans;
for(int i = l ; i <= r ; i++){
if(l <= L[x + 1][i] && L[x + 1][i] + 1 != i) ans.push_back({L[x + 1][i] , i});
if(R[x + 1][i] <= r && i + 1 != R[x + 1][i]) ans.push_back({i , R[x + 1][i]});
}
for(int i = x + 2 ; i < y ; i++){
vector<pii> cur;
for(pii j : ans){
int a = j.first , b = j.second;
if(R[i][a] == b || L[i][b] == a) cur.push_back(j);
}
ans = cur;
}
// cout << x << sep << y << sep << l << sep << r << sep << SZ(ans) << endl;
return SZ(ans);
}
ll count_rectangles(vector<vector<int>> a) {
for(int i = 0 ; i < MAXN ; i++){
fill(L[i] , L[i] + MAXN , -1);
fill(R[i] , R[i] + MAXN , MOD);
}
n = SZ(a) , m = SZ(a[0]); ll ans = 0;
for(int i = 1 ; i + 1 < n ; i++){
vector<int> stk;
for(int j = 0 ; j < m ; j++){
int flag = 0;
while(SZ(stk) && a[i][j] >= a[i][stk.back()]){
vec[stk.back()][j].push_back(i);
if(a[i][j] == a[i][stk.back()]) flag = 1;
// cout << stk.back() << sep << j << sep << i << endl;
stk.pop_back();
}
if(SZ(stk) && flag == 0) vec[stk.back()][j].push_back(i);
stk.push_back(j);
}
}
for(int i = 0 ; i < m ; i++){
vector<int> stk;
for(int j = 0 ; j < n ; j++){
int flag = 0;
while(SZ(stk) && a[j][i] >= a[stk.back()][i]){
R[i][stk.back()] = j;
if(a[j][i] == a[stk.back()][i]) flag = 1;
stk.pop_back();
}
if(SZ(stk) && flag == 0) L[i][j] = stk.back();
stk.push_back(j);
}
}
for(int i = 0 ; i < m ; i++){
for(int j = i + 2 ; j < m ; j++){
vec[i][j].push_back(MOD);
int first = -1;
for(int k = 0 ; k < SZ(vec[i][j]) ; k++){
if(k == 0 || vec[i][j][k] != vec[i][j][k - 1] + 1){
if(first != -1) ans += solve(i , j , first - 1 , vec[i][j][k - 1] + 1);
first = vec[i][j][k];
}
}
}
}
return ans;
}
