#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int bit[2505];
void update(int x, int val) {
for(x++; x <= 2500; x += x&-x)
bit[x] += val;
}
int query(int x) {
x++;
int cnt = 0;
while(x > 0) {
cnt += bit[x];
x -= x&-x;
}
return cnt;
}
ll count_rectangles(vector<vector<int>> a) {
int n = sz(a), m = sz(a[0]);
// primeiro eu calculo os pares uteis
vector<pii> line[n][m], col[n][m];
// calculando os pares na linha
vector<int> r(max(n,m));
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
r[j] = j-1;
// acho o primeiro cara maior ou igual (com indice menor)
while(r[j] >= 0 and a[i][r[j]] < a[i][j]) r[j] = r[r[j]];
if(r[j] >= 0 and r[j]+1 < j) line[i][j].pb({r[j], i});
}
for(int j = m-1; j >= 0; j--) {
r[j] = j+1;
// acho o primeiro cara maior ou igual (com indice maior)
while(r[j] < m and a[i][r[j]] < a[i][j]) r[j] = r[r[j]];
if(r[j] < m and j+1 < r[j] and a[i][j] != a[i][r[j]]) line[i][r[j]].pb({j, i});
}
}
// calculando os pares na coluna
for(int j = 0; j < m; j++) {
for(int i = 0; i < n; i++) {
r[i] = i-1;
// acho o primeiro cara maior ou igual (com indice menor)
while(r[i] >= 0 and a[r[i]][j] < a[i][j]) r[i] = r[r[i]];
if(r[i] >= 0 and r[i]+1 < i) col[i][j].pb({r[i], j});
}
for(int i = n-1; i >= 0; i--) {
r[i] = i+1;
// acho o primeiro cara maior ou igual (com indice maior)
while(r[i] < n and a[r[i]][j] < a[i][j]) r[i] = r[r[i]];
if(r[i] < n and i+1 < r[i] and a[i][j] != a[r[i]][j]) col[r[i]][j].pb({i, j});
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
sort(all(line[i][j]));
sort(all(col[i][j]));
for(int k = 0, ptr = 0; i != 0 and k < sz(line[i][j]); k++) {
while(ptr < sz(line[i-1][j]) and line[i-1][j][ptr].fr < line[i][j][k].fr) ptr++;
if(ptr >= sz(line[i-1][j])) break;
if(line[i-1][j][ptr].fr == line[i][j][k].fr) line[i][j][k].sc = line[i-1][j][ptr].sc;
}
for(int k = 0, ptr = 0; j != 0 and k < sz(col[i][j]); k++) {
while(ptr < sz(col[i][j-1]) and col[i][j-1][ptr].fr < col[i][j][k].fr) ptr++;
if(ptr >= sz(col[i][j-1])) break;
if(col[i][j-1][ptr].fr == col[i][j][k].fr) col[i][j][k].sc = col[i][j-1][ptr].sc;
}
}
}
// Toda parte anterior é em O(n*m*log)
// Parte que calcula a resposta em O(n*m*min(n,m))
int ans = 0;
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) {
// aqui nos calculamos os retangulos com canto inferior direito (i,j), ou seja:
// (i,j-1), (i,j-2), ..., (i,j-x) fazem parte da borda do retangulo
// (i-1,j), (i-2,j), ..., (i-y,j) fazem parte da borda retangulo
vector<pii> A = col[i][j-1], B = line[i-1][j];
if(!sz(A) or !sz(B)) continue;
for(auto &[x,y] : A) x++;
sort(all(A));
for(auto &[x,y] : B) x++, swap(x,y);
sort(all(B));
for(int i = 0, j = 0; i < sz(A); i++) {
while(j < sz(B) and B[j].fr <= A[i].fr)
update(B[j].sc, 1), j++;
ans += query(2499) - query(A[i].sc - 1);
if(i != sz(A)-1) continue;
while(j > 0) j--, update(B[j].sc, -1);
}
}
}
return ans;
}
