#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
int r, c;
const int dx[4] = {1, -1, 0, 0};
const int dy[4] = {0, 0, 1, -1};
ll count_rectangles(vector<vector<int>> arr) {
r = size(arr);
c = size(arr[0]);
vector<vector<int>> maxUp(r, vector<int>(c, -1));
vector<vector<int>> maxDown(r, vector<int>(c, -1));
vector<vector<int>> maxLeft(r, vector<int>(c, -1));
vector<vector<int>> maxRight(r, vector<int>(c, -1));
for(int y = 0; y < r; y++) {
for(int x = 0; x < c; x++) {
int xl = x-1, xr = x+1;
int yu = y-1, yd = y+1;
for(; xl >= 0; xl--) if(arr[y][xl] > arr[y][x]) break;
for(; xr < c; xr++) if(arr[y][xr] > arr[y][x]) break;
for(; yu >= 0; yu--) if(arr[yu][x] > arr[y][x]) break;
for(; yd < r; yd++) if(arr[yd][x] > arr[y][x]) break;
maxUp[y][x] = yu;
maxDown[y][x] = yd;
maxLeft[y][x] = xl;
maxRight[y][x] = xr;
}
}
vector<vector<int>> vis(r, vector<int>(c, 0));
int thing = 1;
ll ans = 0;
for(int y = 1; y < r-1; y++) {
for(int x = 1; x < c-1; x++) {
int mnX = maxLeft[y][x], mxX = maxRight[y][x], mxY = maxDown[y][x], mnY = maxUp[y][x];
int mnX2, mxX2, mnY2, mxY2;
mnX2 = mxX2 = x;
mnY2 = mxY2 = y;
vis[y][x] = thing;
int sz = 1;
queue<pair<int, int>> bfs;
bfs.push(make_pair(y, x));
while(!bfs.empty()) {
pair<int, int> curr = bfs.front(); bfs.pop();
for(int i = 0; i < 4; i++) {
int ny = curr.first + dy[i];
int nx = curr.second + dx[i];
if(0 <= ny && ny < r && 0 <= nx && nx < c) if(vis[ny][nx] != thing) if(arr[curr.first][curr.second] >= arr[ny][nx]) {
bfs.push(make_pair(y, x));
mnX = min(maxLeft[ny][nx], mnX);
mxX = max(maxRight[ny][nx], mxX);
mnY = min(maxUp[ny][nx], mnY);
mxY = max(maxDown[ny][nx], mxY);
mnX2 = min(mnX2, nx);
mxX2 = max(mxX2, nx);
mnY2 = min(mnY2, ny);
mxY2 = max(mxY2, ny);
vis[ny][nx] = thing;
sz++;
}
}
}
// cout << x << ' ' << y << '\n';
// cout << sz << '\n';
// cout << mnX2 << ' ' << mxX2 << '\n';
// cout << mnY2 << ' ' << mxY2 << '\n';
// cout << mnX << ' ' << mxX << '\n';
// cout << mnY << ' ' << mxY << '\n';
if(sz == (mxX2 - mnX2 + 1) * (mxY2 - mnY2 + 1)) if(mnX + 1 == mnX2) if(mxX - 1 == mxX2) if(mnY + 1 == mnY2) if(mxY - 1 == mxY2) if(0 != mnY2 && mnY2 != r-1 && 0 != mnX2 && mnX2 != c-1) {
// cout << "added\n";
ans++;
}
// cout << '\n';
thing++;
}
}
return ans;
}
