#include <bits/stdc++.h>
#include "rect.h"
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")
using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<int>;
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lb lower_bound
const int oo = 1000 * 1000 * 1000 + 7;
int ST[40004], SP[120][120], SG[120][120];
void update(int v, int l, int r, int p, int val) {
if(l == r) {
ST[v] = val;
return;
}
int md = (l + r) / 2;
if(p <= md) update(v * 2, l, md, p, val);
else update(v * 2 + 1, md + 1, r, p, val);
ST[v] = max(ST[v * 2], ST[v * 2 + 1]);
}
void update(int c, int v, int l, int r, int p, int val) {
if(l == r) {
SP[v][c] = val;
return;
}
int md = (l + r) / 2;
if(p <= md) update(c, v * 2, l, md, p, val);
else update(c, v * 2 + 1, md + 1, r, p, val);
SP[v][c] = max(SP[v * 2][c], SP[v * 2 + 1][c]);
}
void Update(int c, int v, int l, int r, int p, int val) {
if(l == r) {
SG[v][c] = val;
return;
}
int md = (l + r) / 2;
if(p <= md) Update(c, v * 2, l, md, p, val);
else Update(c, v * 2 + 1, md + 1, r, p, val);
SG[v][c] = max(SG[v * 2][c], SG[v * 2 + 1][c]);
}
int query(int v, int l, int r, int lo, int hi) {
if(l > hi || r < lo) return 0;
if(l >= lo && r <= hi) return ST[v];
return max(query(v * 2, l, (l + r) / 2, lo, hi),
query(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
}
int query(int c, int v, int l, int r, int lo, int hi) {
if(l > hi || r < lo) return 0;
if(l >= lo && r <= hi) return SP[v][c];
return max(query(c, v * 2, l, (l + r) / 2, lo, hi),
query(c, v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
}
int Query(int c, int v, int l, int r, int lo, int hi) {
if(l > hi || r < lo) return 0;
if(l >= lo && r <= hi) return SG[v][c];
return max(Query(c, v * 2, l, (l + r) / 2, lo, hi),
Query(c, v * 2 + 1, (l + r) / 2 + 1, r, lo, hi));
}
ll count_rectangles(vector<vector<int>> A) {
int N = A.size(), M = A[0].size();
ll res = 0;
if(N == 3) {
for(int l = 1; l < M - 1; l++) {
if(A[1][l] >= A[0][l] || A[1][l] >= A[2][l])
update(1, 0, M - 1, l, 1000000007);
else update(1, 0, M - 1, l, A[1][l]);
}
for(int l = 1; l < M - 1; l++) {
for(int i = l; i < M - 1; i++) {
int V = query(1, 0, M - 1, l, i);
res += (V < A[1][l - 1] && V < A[1][i + 1]);
}
}
}
if(N > 3) {
for(int l = 1; l < N - 1; l++)
for(int i = 1; i < M - 1; i++)
update(l, 1, 0, M - 1, i, A[l][i]),
Update(i, 1, 0, N - 1, l, A[l][i]);
for(int l = 1; l < N - 1; l++)
for(int i = 1; i < M - 1; i++)
for(int j = l; j < N - 1; j++)
for(int k = i; k < M - 1; k++) {
bool ok = 1;
for(int x = l; x <= j; x++) {
int V = query(x, 1, 0, M - 1, i, k);
ok &= (V < A[x][i - 1] && V < A[x][k + 1]);
}
for(int y = i; y <= k; y++) {
int V = Query(y, 1, 0, N - 1, l, j);
ok &= (V < A[l - 1][y] && V < A[j + 1][y]);
}
res += ok;
}
}
return res;
}
