#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long ll;
const int N = 2505, LG = 10;
int n, m, row[N][N][LG], col[N][N][LG];
int get_row(int r, int c1, int c2){
int lg = 31 - __builtin_clz(c2 - c1 + 1);
return max(row[r][c1][lg], row[r][c2 - (1 << lg) + 1][lg]);
}
int get_col(int c, int r1, int r2){
int lg = 31 - __builtin_clz(r2 - r1 + 1);
return max(col[c][r1][lg], col[c][r2 - (1 << lg) + 1][lg]);
}
ll count_rectangles(vector<vector<int>> a){
n = a.size(), m = a[0].size();
ll ans = 0;
if (n < 3 or m < 3) return 0;
for (int i = 1; i + 1 < n; i ++){
for (int j = 1; j + 1 < m; j ++)
row[i][j][0] = a[i][j];
for (int j = 1; j < LG; j ++)
for (int k = 1; k + 1 < m and k + (1 << (j - 1)) < m; k ++)
row[i][k][j] = max(row[i][k][j - 1], row[i][k + (1 << (j - 1))][j - 1]);
}
for (int i = 1; i + 1 < m; i ++){
for (int j = 1; j + 1 < n; j ++)
col[i][j][0] = a[j][i];
for (int j = 1; j < LG; j ++)
for (int k = 1; k + 1 < n and k + (1 << (j - 1)) < n; k ++)
col[i][k][j] = max(col[i][k][j - 1], col[i][k + (1 << (j - 1))][j - 1]);
}
bool good[n] = {};
for (int c1 = 1; c1 + 1 < m; c1 ++){
for (int c2 = c1; c2 + 1 < m; c2 ++){
memset(good, 0, sizeof good);
for (int r = 1; r + 1 < n; r ++){
int mx = get_row(r, c1, c2);
good[r] = (a[r][c1 - 1] > mx and a[r][c2 + 1] > mx);
}
for (int r1 = 1; r1 + 1 < n; r1 ++){
if (!good[r1]) continue;
for (int r2 = r1; r2 + 1 < n; r2 ++){
if (!good[r2]) break;
bool all_good = 1;
for (int c = c1; c <= c2 and all_good; c ++){
int mx = get_col(c, r1, r2);
all_good &= (a[r1 - 1][c] > mx and a[r2 + 1][c] > mx);
}
ans += all_good;
}
}
}
}
return ans;
}
