#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
int n, m;
bool valid(int x, int y) {
if (x >= 0 && x<n && y >= 0 && y < m) return true;
else return false;
}
struct SegTree {
vector<int> tree;
SegTree(int n) {
tree.assign(4*n, 0);
}
void query(int p, int l, int r, int i, int x) {
if (l > i || r < i) return;
if (l==r && l==i) {
tree[p] = x;
}
else {
int m = (l+r)/2;
query(2*p, l, m, i, x);
query(2*p+1, m+1, r, i, x);
tree[p] = max(tree[2*p], tree[2*p+1]);
}
}
int rmq(int p, int l, int r, int i, int j) {
if (l > j || r < i) return 0;
if (i<=l && r <= j) {
return tree[p];
}
int m = (l+r)/2;
int i1 = rmq(2*p, l, m, i, j);
int i2 = rmq(2*p+1, m+1, r, i, j);
return max(i1, i2);
}
};
ll count_rectangles(vector<vector<int>> a) {
int n = a.size();
int m = a.size();
ll cnt=0;
for (int i1=1; i1<n-1; i1++) {
for (int j1=1; j1<m-1; j1++) {
for (int i2=i1; i2<n-1; i2++) {
for (int j2 = j1; j2<m-1; j2++) {
bool can=true;
for (int i=i1; i<=i2; i++) {
for (int j=j1; j<=j2; j++) {
if (a[i][j] < a[i1-1][j] && a[i][j] < a[i2+1][j] && a[i][j] < a[i][j1-1] && a[i][j] < a[i][j2+1]) {
can = true;
}
else {
can = false;
break;
}
}
if (!can) break;
}
if (can) cnt++;
}
}
}
}
return cnt;
}
