#include <bits/stdc++.h>
#include "rect.h"
using ll = long long;
using namespace std;
const int MAXN = 2510;
int mat[MAXN][MAXN];
int row[MAXN][MAXN][2], col[MAXN][MAXN][2];
// row[i][j] = primeiro linha (para cima) que tem val >=
// col[i][j] = primeira coluna (para esquerda) que tem val >=
int n, m;
ll solve_3(){
ll ans = 0;
for(int i=1; i<=m; i++){
for(int j=(i + 1); j<col[i][2][1]; j++){
if(mat[2][i] >= mat[1][i] || mat[2][i] >= mat[3][i]) break;
ans ++;
}
}
return ans;
}
ll count_rectangles(vector<vector<int>> a){
n = (int) a.size();
m = (int) a[0].size();
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
mat[i + 1][j + 1] = a[i][j];
}
}
for(int i=1; i<=n; i++){
stack<int> q;
for(int j=1; j<=m; j++){
while(!q.empty() && mat[i][q.top()] < mat[i][j]) q.pop();
if(!q.empty()) col[i][j][0] = q.top();
else col[i][j][0] = 1;
q.push(j);
}
}
for(int i=1; i<=n; i++){
stack<int> q;
for(int j=m; j>=1; j--){
while(!q.empty() && mat[i][q.top()] < mat[i][j]) q.pop();
if(!q.empty()) col[i][j][1] = q.top();
else col[i][j][1] = m;
q.push(j);
}
}
for(int j=1; j<=m; j++){
stack<int> q;
for(int i=1; i<=n; i++){
while(!q.empty() && mat[q.top()][j] < mat[i][j]) q.pop();
if(!q.empty()) row[i][j][0] = q.top();
else row[i][j][0] = 1;
q.push(i);
}
}
for(int j=1; j<=m; j++){
stack<int> q;
for(int i=n; i>=1; i--){
while(!q.empty() && mat[q.top()][j] < mat[i][j]) q.pop();
if(!q.empty()) row[i][j][1] = q.top();
else row[i][j][1] = n;
q.push(i);
}
}
/*
cout << "***row***" << endl;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cout << i << " " << j << " " << row[i][j] << endl;
}
}
cout << "***col***" << endl;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
cout << i << " " << j << " " << col[i][j] << endl;
}
}
*/
// cout << "calculei row / col" << endl;
// n * (m * m)
if(n == 3) return solve_3();
ll ans = 0;
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
int min_col = 1;
for(int k=(i - 2); k>=1; k--){
min_col = max(min_col, col[k + 1][j][0]);
for(int l=(j - 1); l>min_col; l--){
if(row[i][l][0] <= k && row[k][l][1] >= i){
bool ok = true;
for(int x=(k + 1); x<i; x++){
if(col[x][l - 1][1] < j){
ok = false;
}
}
// cout << "(" << k + 1 << ", " << l << "), (" << i - 1 << ", " << j - 1 << ")" << endl;
if(ok) ans ++;
} else break;
}
}
}
}
return ans;
}
