#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops,inline-functions")
#define sz(v) (int)(v).size()
typedef long long ll;
const int INF = 1e9;
ll sum(ll x) {
return x * (x+1) / 2;
}
int n, m;
ll count_rectangles(vector<vector<int>> mat) {
n = sz(mat); m = sz(mat[0]);
ll ans = 0;
for (int i1=1; i1<n-1; i1++) {
for (int i2=i1; i2<n-1; i2++) {
for (int j1=1; j1<m-1; j1++) {
vector<int> mx(n, -INF);
for (int j2=j1; j2<m-1; j2++) {
bool can = true, stop = false;
for (int i=i1; i<=i2; i++) {
if (mat[i][j2] >= min(mat[i1-1][j2], mat[i2+1][j2])) {
can = false;
stop = true;
}
mx[i] = max(mx[i], mat[i][j2]);
if (mx[i] >= mat[i][j1-1]) can = false, stop = true;
if (mx[i] >= mat[i][j2+1]) can = false;
}
if (stop) break;
// if (can) cout << i1 << ' ' << j1 << '\n';
ans += can;
}
}
}
}
return ans;
}
