#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;
const int MAXN = 3510, MAXK = 13;
int n, m;
int colMax[MAXN][MAXN][MAXK];
int rowMax[MAXN][MAXN][MAXK];
int lg[MAXN];
void buildST() {
FOR(i, 2, MAXN-1) lg[i] = lg[i/2]+1;
FOR(j, 1, MAXK-1) FOR(k, 0, m-1) for (int i = 0; i + (1<<j) <= n; i++) {
colMax[k][i][j] = max(colMax[k][i][j-1], colMax[k][i + (1<<(j-1))][j-1]);
}
FOR(j, 1, MAXK-1) FOR(k, 0, n-1) for (int i = 0; i + (1<<j) <= m; i++) {
rowMax[k][i][j] = max(rowMax[k][i][j-1], rowMax[k][i + (1<<(j-1))][j-1]);
}
}
int getColMax (int k, int fr, int to) {
int j = lg[to-fr+1];
return max(colMax[k][fr][j], colMax[k][to - (1<<j)+ 1][j]);
}
int getRowMax (int k, int fr, int to) {
int j = lg[to-fr+1];
return max(rowMax[k][fr][j], rowMax[k][to - (1<<j)+ 1][j]);
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = (int)a.size();
m = (int)a[0].size();
FOR(i, 0, n-1) FOR(j, 0, m-1) colMax[j][i][0] = rowMax[i][j][0] = a[i][j];
buildST();
/*FOR(r1, 0, n-1) FOR(c1, 0, m-1) FOR(r2, r1, n-1) {
cout << " colMax, col: " << c1 << " ["<<r1<<", "<<r2<<"] mx= " << getColMax(c1, r1, r2) << endl;
}
FOR(r1, 0, n-1) FOR(c1, 0, m-1) FOR(c2, c1, m-1) {
cout << " rowMax, row: " << r1 << " ["<<c1<<", "<<c2<<"] mx= " << getRowMax(r1, c1, c2) << endl;
}*/
ll ans = 0ll;
FOR(r1, 1, n-2) FOR(c1, 1, m-2) FOR(r2, r1, n-2) FOR(c2, c1, m-2) {
bool ok = true;
/*FOR(i, r1, r2) FOR(j, c1, c2) {
int mnH = a[i][c1-1];
mnH = min(mnH, a[i][c2+1]);
mnH = min(mnH, a[r1-1][j]);
mnH = min(mnH, a[r2+1][j]);
if(a[i][j] >= mnH) {
ok = false;
break;
}
}*/
FOR(i, r1, r2) {
int mnH = min(a[i][c1-1], a[i][c2+1]);
int mxH = getRowMax(i, c1, c2);
if (mxH >= mnH) {
ok = false;
break;
}
}
if (ok) {
FOR(j, c1, c2) {
int mnH = min(a[r1-1][j], a[r2+1][j]);
int mxH = getColMax(j, r1, r2);
if(mxH >= mnH) {
ok = false;
break;
}
}
}
if (ok) ans++;
}
return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
ans:
6
*/
