#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 202;
const int M = N * N;
const int di[] = {0, 0, 1, -1};
const int dj[] = {1, -1, 0, 0};
int n, m;
vector<vector<int>> a;
long long count_rectangles(std::vector<std::vector<int> > A) {
n = (int) A.size();
m = (int) A[0].size();
a = A;
vector<vector<vector<int>>> rows(n, vector<vector<int>> (m, vector<int> (m)));
for (int i = 1; i < n - 1; ++i) {
for (int j = 1; j < m - 1; ++j) {
int mx = 0;
for (int k = j; k < m - 1; ++k) {
mx = max(mx, a[i][k]);
rows[i][j][k] = mx;
}
}
}
vector<vector<vector<int>>> cols(m, vector<vector<int>> (n, vector<int> (n)));
for (int i = 1; i < m - 1; ++i) {
for (int j = 1; j < n - 1; ++j) {
int mx = 0;
for (int k = j; k < n - 1; ++k) {
mx = max(mx, a[k][i]);
cols[i][j][k] = mx;
}
}
}
auto check = [&](int x, int xx, int y, int yy) {
for (int i = x; i <= xx; ++i) {
if (rows[i][y][yy] >= a[i][y - 1] || rows[i][y][yy] >= a[i][yy + 1]) {
return false;
}
}
for (int i = y; i <= yy; ++i) {
if (cols[i][x][xx] >= a[x - 1][i] || cols[i][x][xx] >= a[xx + 1][i]) {
return false;
}
}
return true;
};
long long ans = 0;
for (int i = 1; i < n - 1; ++i) {
for (int j = i; j < n - 1; ++j) {
for (int k = 1; k < m - 1; ++k) {
for (int l = k; l < m - 1; ++l) {
ans += check(i, j, k, l);
}
}
}
}
return ans;
}
