#include <bits/stdc++.h>
#include "rect.h"
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using ld = long double;
//#define int ll
#define sz(x) ((int)(x).size())
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 25e2 + 5;
#define lsb(x) (x & -x)
struct AIB {
vector<int> v;
vector<pii> st;
void init(int n) {
v.assign(n + 3, 0);
st.clear();
}
template<int reverser = 0> void upd(int p, int x) {
if(!reverser) st.emplace_back(p, x);
++p;
while(p < sz(v)) v[p] += x, p += lsb(p);
}
int query(int p) {
++p;
int sum = 0;
while(p > 0) sum += v[p], p -= lsb(p);
return sum;
}
int gettime() { return sz(st); }
void revert() {
if(!sz(st)) return;
auto [a, b] = st.back();
upd<1>(a, -b);
st.pop_back();
}
void revert(int btime) {
while(gettime() > btime) revert();
}
};
AIB aib;
struct RangeCounter {
pii mat[nmax][nmax];
void init(int n) { for(int i = 0; i < n; i++) for(int j = i; j < n; j++) mat[i][j].second = -100; }
void addright(int l, int r, int R) {
if(r - l <= 1) return;
//cerr << "\n(******)\nadding " << l << ' ' << r << '\t' << R << "\n(******)\n";
if(mat[l][r].second != R - 1) mat[l][r].first = R;
mat[l][r].second = R;
}
int qleft(int l, int r) { return mat[l][r].first - 1; }
};
RangeCounter hori, verti;
long long count_rectangles(std::vector<std::vector<int>> mat) {
ll rez = 0;
int n = sz(mat), m = sz(mat[0]);
hori.init(m + 1);
verti.init(n + 1);
aib.init(max(n, m) + 2);
vector<vector<int>> colst(m, vector<int>());
auto addcolcell = [&](vector<int>& leftcol, int i, int j) {
//cerr << "Pentru verticale::\n";
int lst = -12918;
while(1) {
if(colst[j].empty()) break;
if(lst != mat[i][j]) {
if(colst[j].back() < i - 1) leftcol.emplace_back(colst[j].back());
verti.addright(colst[j].back(), i, j);
}
if(!(mat[colst[j].back()][j] <= mat[i][j])) break;
lst = mat[colst[j].back()][j];
colst[j].pop_back();
}
colst[j].emplace_back(i);
};
vector<int> sdfiasfifas_tmp;
for(int i = 0; i < 2; i++)
for(int j = 0; j < m; j++)
addcolcell(sdfiasfifas_tmp, i, j);
for(int i = 1; i < n - 1; i++) {
vector<int> rowst;
for(int j = 0; j < m; j++) {
vector<int> leftcol, leftrow; // left pe row sau pe col
{
int lst = -129423;
while(1) {
if(rowst.empty()) break;
if(lst != mat[i][j]) {
if(rowst.back() < j - 1) leftrow.emplace_back(rowst.back());
hori.addright(rowst.back(), j, i);
}
if(!(mat[i][rowst.back()] <= mat[i][j])) break;
lst = mat[i][rowst.back()];
rowst.pop_back();
}
rowst.emplace_back(j);
}
if(j >= 2) {
addcolcell(leftcol, i + 1, j - 1);
sort(all(leftrow), [&](int a, int b) { return hori.qleft(a, j) > hori.qleft(b, j); });
int p = 0;
aib.revert(0);
for(auto x : leftrow) {
while(p < sz(leftcol) && hori.qleft(x, j) <= leftcol[p])
aib.upd(verti.qleft(leftcol[p], i + 1), 1), ++p;
rez += aib.query(x);
}
}
}
}
return rez;
}
/**
Istenem! Nu poate fi real.
-- Surse verificate
*/
