#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
using vi = vector<int>;
using i4 = array<int, 4>;
using vi4 = vector<i4>;
void extract(int n, int m, vector<vi> &V, vi4 &V1) {
vector<stack<int> > lin(m);
for(int j = 0; j < m; ++j)
lin[j].push(0);
set<int> Cur;
for(int i = 1; i < n; ++i) {
vector<pair<int, int> > Ult, UrmU; /// perechi (linie, j din trecut)
for(int j = 0; j < m; ++j) {
Cur.clear();
int uv = -1;
while(!lin[j].empty() && V[i][j] >= V[lin[j].top()][j]) {
if(V[lin[j].top()][j] != uv) {
Cur.insert(lin[j].top());
uv = V[lin[j].top()][j];
}
lin[j].pop();
}
if(!lin[j].empty()) {
if(V[lin[j].top()][j] != uv) { // desc
Cur.insert(lin[j].top());
uv = V[lin[j].top()][j];
}
}
lin[j].push(i);
UrmU.clear();
for(auto [l, jv] : Ult) {
if(Cur.count(l)) {
UrmU.push_back({l, jv});
Cur.erase(l);
} else {
if(abs(l - i) > 1)
V1.push_back(i4{l, i, jv, j - 1});
}
}
swap(Ult, UrmU);
for(auto vc : Cur)
Ult.push_back({vc, j});
}
for(auto [l, jv] : Ult) {
if(abs(l - i) > 1)
V1.push_back(i4{l, i, jv, m - 1});
}
}
}
long long count_rectangles(std::vector<std::vector<int> > V) {
int n = V.size(), m = V[0].size();
vector<vi> VT(m, vi(n, 0));
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
VT[j][i] = V[i][j];
vi4 V1, V2;
extract(n, m, V, V1);
extract(m, n, VT, V2);
for(auto &it : V2) {
swap(it[0], it[2]);
swap(it[1], it[3]);
}
for(auto &it : V1) {
--it[2];
++it[3];
}
for(auto &it : V2) {
--it[0];
++it[1];
}
int re = 0;
for(auto it1 : V1) {
for(auto it2 : V2) {
int ok = 1;
for(int i = 0; i < 4; ++i) {
int sgn = 1;
if(i > 1 && i < 3) sgn = -1;
if(it2[i] * sgn >= it1[i] * sgn);
else ok = 0;
}
re += ok;
}
}
return re;
}
