#include "rect.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
// #define int LL
using namespace std;
using LL = long long;
using pii = pair<int, int>;
const int MAXN = 2510;
int n, m;
int g[MAXN][MAXN];
bitset<MAXN> pure[MAXN];
bitset<MAXN> vis[MAXN];
struct OWO {
int far, pure, cnt, l, r, u, d;
bool check() {
if(far || !pure) return false;
int w = r - l + 1;
int h = d - u + 1;
return w * h == cnt;
}
void out() {
cout << "owo: ";
if(far || !pure) cout << "far\n";
else {
cout << cnt << " (";
cout << l << "-" << r << ", ";
cout << u << "-" << d << ")\n";
}
}
};
OWO merge(const OWO &a, const OWO &b) {
return (OWO){
a.far || b.far,
a.pure || b.pure,
a.cnt + b.cnt,
min(a.l, b.l),
max(a.r, b.r),
min(a.u, b.u),
max(a.d, b.d)
};
}
// 0 for ok
// 1 for boundary
// 2 for outside
int check(int x, int y) {
if(x < 0 || x >= n || y < 0 || y >= m) return 2;
if(x == 0 || x == n - 1 || y == 0 || y == m - 1) return 1;
return 0;
}
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
OWO dfs(int sx, int sy) {
vis[sx][sy] = 1;
OWO owo = (OWO){0, 0, 0, sx, sx, sy, sy};
queue<pii> que;
que.emplace(sx, sy);
while(!que.empty()) {
int x, y;
tie(x, y) = que.front();
que.pop();
owo = merge(owo, (OWO){0, pure[x][y], 1, x, x, y, y});
For(it, 0, 3) {
int nx = x + dx[it];
int ny = y + dy[it];
if(check(nx, ny) == 2) continue;
if(vis[nx][ny] == 0) {
vis[nx][ny] = 1;
que.emplace(nx, ny);
}
}
if(check(x, y) == 1) {
owo.far = 1;
}
}
return owo;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
n = sz(a);
m = sz(a[0]);
assert(max(n, m) <= 200);
vector<pair<int, pii>> v;
For(i, 0, n - 1) For(j, 0, m - 1) {
g[i][j] = a[i][j];
v.eb(g[i][j], pii(i, j));
// assert(g[i][j] < 2);
}
sort(all(v));
LL ans = 0;
while(sz(v)) {
int val = v.back().F;
vector<pii> pos;
while(sz(v) && v.back().F == val) {
pos.eb(v.back().S);
v.pop_back();
auto &p = pos.back();
pure[p.F][p.S] = 1;
}
For(i, 0, n - 1) vis[i].reset();
For(i, 0, n - 1) For(j, 0, m - 1) {
if(g[i][j] > val) vis[i][j] = 1;
// cout << vis[i][j] << " \n"[j == m - 1];
}
For(i, 1, n - 2) For(j, 1, m - 2) if(vis[i][j] == 0) {
auto owo = dfs(i, j);
ans += owo.check();
// owo.out();
}
for(auto &p:pos) {
pure[p.F][p.S] = 0;
}
}
return ans;
}
