#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 998244353;
const ll INF = 1e18;
const ld EPS = 1e-12;
#define endl "\n"
#define sp <<" "<<
#define REP(i, a, b) for(ll i = a; i < b; i++)
#define dbg(x) cout << #x << " = " << x << endl
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define fast_io() ios_base::sync_with_stdio(false); cin.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((ll)(x).size())
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template <typename Key, typename Value>
using hash_map = unordered_map<Key, Value, custom_hash>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// uniform_int_distribution<int>(a, b)(rng);
// shuffle(all(a), rng);
// d, u, r, l
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
ll count_rectangles(vector<vector<int>> a) {
ll n = a.size(), m = a[0].size();
ll ans = 0, curr;
assert(n <= 30 and m <= 30);
vector<pair<int, int>> b(n*m);
REP(i, 0, n) {
REP(j, 0, m) {
b[i*m+j] = {a[i][j], i*m+j};
}
}
sort(all(b));
vector<vector<bool>> vis(n, vector<bool>(m, false)), good;
good = vis;
auto in = [&](int x, int y) -> bool {
return (0 < x and x < n-1 and 0 < y and y < m-1);
};
auto check = [&](int x, int y) -> bool {
return (0 <= x and x < n and 0 <= y and y < m);
};
auto bfs = [&](auto &&bfs, int xx, int yy) -> void {
queue<int> q;
q.push(xx*m+yy);
// vis[xx][yy] = true;
while (!q.empty()) {
int r = q.front(); q.pop();
int x = r / m, y = r % m;
if (vis[x][y] or good[x][y]) continue;
vis[x][y] = true;
bool ok = true;
array<bool, 4> dir = {false, false, false, false};
int nx[4], ny[4];
REP(i, 0, 4) {
nx[i] = x + dx[i], ny[i] = y + dy[i];
}
// d, u, r, l
if (xx - x > 0) {
nx[0] += xx - x;
dir[0] = true;
} else if (xx - x < 0) {
nx[1] -= x - xx;
dir[1] = true;
}
if (yy - y > 0) {
ny[2] += yy - y;
dir[2] = true;
} else if (yy - y < 0) {
ny[3] -= y - yy;
dir[3] = true;
}
REP(i, 0, 4) {
int nxx = nx[i], nyy = ny[i];
// if (x == 3 and y == 2) cerr << dir[i] sp nxx sp nyy << endl;
if (check(nxx, nyy)) {
if (!dir[i] and !good[x+dx[i]][y+dy[i]] and a[nxx][nyy] <= a[x][y]) {
ok = false;
break;
} else if (dir[i] and a[nxx][nyy] <= a[x][y]) {
ok = false;
break;
}
}
}
if (ok) {
good[x][y] = true;
REP(i, 0, 4) {
int nxx = nx[i], nyy = ny[i];
if (in(nxx, nyy) and !vis[nxx][nyy] and !good[nxx][nyy]) {
q.push(nxx*m+nyy);
}
}
curr++;
}
}
};
REP(i, 0, n*m) {
int x = b[i].second / m, y = b[i].second % m;
if (in(x, y) and !vis[x][y]) {
curr = 0;
bfs(bfs, x, y);
ans += curr;
}
}
// REP(i, 0, n) {
// REP(j, 0, m) {
// cerr << good[i][j];
// }
// cerr << endl;
// }
return ans;
}
