#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
int r, c, n;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, -1, 1};
struct DSU{
vector<int> par, sz, minX, maxX, minY, maxY;
vector<bool> invalid, active;
DSU() {
par = sz = minX = maxX = minY = maxY = vector<int>(n, 0);
invalid = active = vector<bool>(n, false);
for(int i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
minX[i] = maxX[i] = (c==0?0:i/c);
minY[i] = maxY[i] = (c==0?i:i%c);
invalid[i] = (i/c == 0 || i/c == r-1 || i%c == 0 || i%c == c-1);
active[i] = false;
}
}
int parent(int n) {
if(par[n] != n) par[n] = parent(par[n]);
return par[n];
}
void merge(int x1, int y1, int x2, int y2) {
int a = parent(y1 + x1*c);
int b = parent(y2 + x2*c);
if(!(active[a] and active[b])) return;
if(a == b) return;
// cout << "merged " << x1 << ' ' << y1 << " to " << x2 << ' ' << y2 << '\n';
if(!(sz[a] > sz[b])) swap(a, b);
sz[a] += sz[b];
par[b] = a;
invalid[a] = invalid[a] | invalid[b];
minX[a] = min(minX[a], minX[b]);
maxX[a] = max(maxX[a], maxX[b]);
minY[a] = min(minY[a], minY[b]);
maxY[a] = max(maxY[a], maxY[b]);
}
void activate(int x, int y) {
// cout << x << ' ' << y << '\n';
assert(y + x*c < n);
active[y + x*c] = true;
// cout << y + x*c << '\n';
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(0 <= nx && nx < c && 0 <= ny && ny < r) merge(x, y, nx, ny);
}
}
void check(int x, int y, ll &an) {
int q = parent(y + x*c);
// cout << x << ' ' << y << '\n';
// cout << y + x*c << ' ' << parent(y + x*c) << '\n';
// cout << sz[q] << '\n';
// cout << minX[q] << ' ' << maxX[q] << ' ' << minY[q] << ' ' << maxY[q] << '\n';
// cout << (maxX[q] - minX[q] + 1) * (maxY[q] - minY[q] + 1) << '\n';
// cout << active[q] << ' ' << invalid[q] << '\n';
if(active[q]) if(sz[q] == (maxX[q] - minX[q] + 1) * (maxY[q] - minY[q] + 1)) if(!invalid[q]) {
// cout << "add!\n";
an++;
}
// cout << '\n';
}
};
struct Element{
int val, x, y;
Element(int a, int b, int c): val(a), x(b), y(c) {};
bool operator<(const Element &other) const {
return val < other.val;
}
};
ll count_rectangles(vector<vector<int>> arr) {
r = size(arr);
c = size(arr[0]);
n = r*c;
vector<Element> a;
for(int i = 0; i < c; i++) {
for(int j = 0; j < r; j++) {
a.push_back(Element(arr[j][i], j, i));
}
}
sort(a.begin(), a.end());
DSU dsutree;
ll ans = 0;
for(int i = 0; i < n; i++) {
if(i) if(a[i].val != a[i-1].val) {
set<int> checked;
for(int x = 0; x < r; x++) {
for(int y = 0; y < c; y++) {
if(dsutree.parent(y + x*c) == y + x*c) if(checked.find(y + x*c) == checked.end()) {
dsutree.check(x, y, ans);
checked.emplace(y + x*c);
}
}
}
}
dsutree.activate(a[i].x, a[i].y);
}
set<int> checked;
for(int x = 0; x < r; x++) {
for(int y = 0; y < c; y++) {
if(dsutree.parent(y + x*c) == y + x*c) if(checked.find(y + x*c) == checked.end()) {
dsutree.check(x, y, ans);
checked.emplace(y + x*c);
}
}
}
return ans;
}
