#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
#define sz(x) (int)(x).size()
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 25e2 + 5, inf = 1e9 + 5;
int dirx[4] = {1, -1, 0, 0};
int diry[4] = {0, 0, 1, -1};
vector<vector<int>> mat, tmp;
vector<pii> list[nmax * nmax];
int n, m, maxv;
#define y1 rgbuih
int x1, x2, y1, y2;
void dfs(int x, int y) {
if(tmp[x][y] != 0) return;
x1 = min(x, x1);
y1 = min(y, y1);
x2 = max(x, x2);
y2 = max(y, y2);
tmp[x][y] = 1;
for(int h = 0; h < 4; h++)
dfs(x + dirx[h], y + diry[h]);
return;
}
ll countforlim(int lim) {
tmp = mat;
vector<vector<int>> spart(n + 2, vector<int>(m + 2, 0));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++)
tmp[i][j] = tmp[i][j] > lim,
spart[i][j] += spart[i - 1][j] + spart[i][j - 1] - spart[i - 1][j - 1];
}
ll count = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(tmp[i][j] != 1 && mat[i][j] == lim) {
x1 = n + 1,
x2 = 0,
y1 = m + 1,
y2 = 0;
dfs(i, j);
if(spart[x2][y2] - spart[x1 - 1][y2] - spart[x2][y1 - 1] + spart[x1 - 1][y1 - 1] == 0 && x1 > 1 && x2 < n && y1 > 1 && y2 < m) {
count++;
//cerr << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << '\t' << lim << ' ' << mat[x1][y1] << '\n';
}
}
}
}
return count;
}
long long count_rectangles(std::vector<std::vector<int> > initmat) {
{ // normalizare
map<int,int> nrm;
for(auto &v : initmat) {
for(auto &x : v)
nrm[x];
}
int cnt = 0;
for(auto &[a, b] : nrm) b = cnt++;
for(auto &v : initmat) {
for(auto &x : v)
x = nrm[x];
}
maxv = cnt - 1;
}
n = initmat.size();
m = initmat[0].size();
mat.resize(n + 2, vector<int>(m + 2, inf));
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
mat[i][j] = initmat[i - 1][j - 1];
}
}
//for(auto v : mat) {
//for(auto x : v)
//cerr << x << ' ';
//cerr << '\n';
//}
ll total = 0;
for(int u = 0; u <= maxv; u++) { // a se schimba la <= maxv
total += countforlim(u);
}
return total;
}
