#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2500 + 10;
vector<pair<int,int>> row[maxn][maxn], col[maxn][maxn];
int pre[maxn];
int dp[maxn][maxn];
long long count_rectangles(vector<vector<int>> a){
int n = a.size(), m = a[0].size();
for (int i = 1; i < n-1; i++){
for (int j = 0; j < m; j++){
pre[j] = j-1;
while (pre[j] != -1 and a[i][j] > a[i][pre[j]])
pre[j] = pre[pre[j]];
if (pre[j] == -1 or a[i][pre[j]] == a[i][j] or pre[j] == j-1)
continue;
row[i][pre[j]+1].push_back({j-1,1});
}
for (int j = m-1; j >= 0; j--){
pre[j] = j+1;
while (pre[j] != m and a[i][j] > a[i][pre[j]])
pre[j] = pre[pre[j]];
if (pre[j] == j+1 or pre[j] == m)
continue;
row[i][j+1].push_back({pre[j]-1,1});
}
}
for (int i = n-2; i >= 0; i--){
for (int j = 0; j < m; j++)
for (auto [x,cnt] : row[i][j])
dp[j][x] = -1 * (dp[j][x]+1);
for (int j = 0; j < m; j++)
for (auto [x,cnt] : row[i+1][j])
if (dp[j][x] > 0)
dp[j][x] = 0;
for (int j = 0; j < m; j++)
for (auto &[x,cnt] : row[i][j])
dp[j][x] *= -1, cnt = dp[j][x];
}
for (int j = 1; j < m-1; j++){
for (int i = 0; i < n; i++){
pre[i] = i-1;
while (pre[i] != -1 and a[i][j] > a[pre[i]][j])
pre[i] = pre[pre[i]];
if (pre[i] == -1 or a[i][j] == a[pre[i]][j] or pre[i] == i-1)
continue;
col[pre[i]+1][j].push_back({i-1,1});
}
for (int i = n-1; i >= 0; i--){
pre[i] = i+1;
while (pre[i] != n and a[i][j] > a[pre[i]][j])
pre[i] = pre[pre[i]];
if (pre[i] == i+1 or pre[i] == n)
continue;
col[i+1][j].push_back({pre[i]-1,1});
}
}
for (int j = m-2; j >= 1; j--){
for (int i = 0; i < n; i++)
for (auto [x,cnt] : col[i][j])
dp[i][x] = -1 * (dp[i][x]+1);
for (int i = 0; i < n; i++)
for (auto [x,cnt] : col[i][j+1])
if (dp[i][x] > 0)
dp[i][x] = 0;
for (int i = 0; i < n; i++)
for (auto &[x,cnt] : col[i][j])
dp[i][x] *= -1, cnt = dp[i][x];
}
ll ret = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
for (auto [x,c1] : row[i][j])
for (auto [y,c2] : col[i][j])
if (c1 >= y-i+1 and c2 >= x-j+1)
ret ++;
return ret;
}
