#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
struct SegTree {
int n; vector<int> arr, st;
SegTree() {};
SegTree(int N, vector<int> &Arr) {
n = N; arr = Arr; st.assign(4*n, INT_MIN);
build(0, 0, n);
}
int build(int i, int l, int r) {
if (l+1 == r) return st[i] = arr[l];
int m = l + (r - l) / 2;
return st[i] = max(build(2*i+1, l, m), build(2*i+2, m, r));
}
int query(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) return INT_MIN;
if (ql <= l && r <= qr) return st[i];
int m = l + (r - l) / 2;
return max(query(2*i+1, l, m, ql, qr), query(2*i+2, m, r, ql, qr));
}
};
ll count_rectangles(vvi a) {
int n = a.size(), m = a[0].size();
vvi b(m, vi(n, INT_MIN)); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) b[j][i] = a[i][j];
vector<SegTree> rows(n), cols(m);
for (int i = 0; i < n; i++) rows[i] = SegTree(m, a[i]);
for (int i = 0; i < m; i++) cols[i] = SegTree(n, b[i]);
ll ans = 0;
for (int x1 = 1; x1 < n-1; x1++) {
for (int x2 = x1; x2 < n-1; x2++) {
for (int y1 = 1; y1 < m-1; y1++) {
for (int y2 = y1; y2 < m-1; y2++) {
bool good = true;
for (int x3 = x1; x3 <= x2; x3++) {
for (int y3 = y1; y3 <= y2; y3++) {
good = good && a[x3][y3] < min({a[x3][y1-1], a[x3][y2+1], a[x1-1][y3], a[x2+1][y3]});
}
}
if (good) ans++;
}
}
}
}
return ans;
}
