#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
typedef long long ll;
const int N = 2500 + 3;
vector<vector<int>> a;
int n, m;
pair<int, int> imp[N][N];
bool check(int x1, int y1, int x2, int y2){
for(int i = x1; i <= x2; ++i)
for(int j = y1; j <= y2; ++j)
if(a[i][j] >= a[x1 - 1][j] || a[i][j] >= a[x2 + 1][j] || a[i][j] >= a[i][y1 - 1] || a[i][j] >= a[i][y2 + 1])
return false;
return true;
}
long long count_rectangles(vector<vector<int>> _a) {
swap(a, _a);
n = a.size(), m = a[0].size();
ll ans = 0;
for(int x1 = 1; x1 < n - 1; ++x1)
for(int y1 = 1; y1 < m - 1; ++y1){
pair<int, int> mx{x1, y1};
int x_lim = n - 2, y_lim = m - 2;
if(imp[x1][y1].first){
x_lim = imp[x1][y1].first;
y_lim = imp[x1][y1].second;
}
for(int x2 = x1; x2 <= x_lim; ++x2)
for(int y2 = y1; y2 <= y_lim; ++y2){
bool b = check(x1, y1, x2, y2);
ans += b;
if(b) mx = max(mx, {x2, y2});
}
for(int x2 = x1; x2 <= mx.first; ++x2)
for(int y2 = y1; y2 <= mx.second; ++y2)
imp[x2][y2] = mx;
}
return ans;
}
