#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 10;
const int maxn = 2500;
class Segment_Tree{
struct Node{
int l, r, u, d; Node( int l = -inf, int r = inf, int u = -inf, int d = inf ) : l(l), r(r), u(u), d(d) {}
Node operator + ( Node n ){
return Node( max( l, n.l ), min( r, n.r ), max( u, n.u ), min( d, n.d ) );
}
};
vector<Node> seg;
void update( int pos, int ini, int fim, int id, Node novo ){
if( ini > id || id > fim ) return;
if( ini == fim ){ seg[pos] = novo; return; }
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
update( l, ini, mid, id, novo ); update( r, mid + 1, fim, id, novo );
seg[pos] = seg[l] + seg[r];
}
Node query( int pos, int ini, int fim, int ki, int kf ){
if( ki > fim || ini > kf ) return seg[0];
if( ki <= ini && fim <= kf ) return seg[pos];
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
return query( l, ini, mid, ki, kf ) + query( r, mid + 1, fim, ki, kf );
}
public:
void update( int id, int l, int r, int u, int d ){
update( 1, 0, maxn, id, Node( l, r, u, d ) );
}
int query( int l, int r, int t ){
Node x = query( 1, 0, maxn, l, r );
if( t == 0 ) return x.u;
if( t == 1 ) return x.r;
if( t == 2 ) return x.d;
return x.l;
}
Segment_Tree() { seg.resize(4*maxn); }
};
Segment_Tree linha[maxn], coluna[maxn];
int l[maxn][maxn], r[maxn][maxn], u[maxn][maxn], d[maxn][maxn];
long long count_rectangles( vector<vector<int>> mat ) {
int n = mat.size(), m = mat[0].size();
for( int i = 0; i < n; i++ ){
stack<pair<int, pair<int, int>>> pilha;
pilha.push({ inf, make_pair(-1, -1) });
for( int j = 0; j < m; j++ ){
l[i][j] = -1; r[i][j] = m;
while( pilha.top().first < mat[i][j] ){
auto [a, b] = pilha.top().second;
r[a][b] = j;
pilha.pop();
}
auto [a, b] = pilha.top().second;
l[i][j] = b;
pilha.push({ mat[i][j], make_pair( i, j ) });
}
for( int j = 0; j < m; j++ ) if( l[i][j] != -1 && mat[i][j] == mat[i][l[i][j]] ) r[i][l[i][j]] = j;
}
for( int j = 0; j < m; j++ ){
stack<pair<int, pair<int, int>>> pilha;
pilha.push({ inf, make_pair(-1, -1) });
for( int i = 0; i < n; i++ ){
u[i][j] = -1; d[i][j] = n;
while( pilha.top().first < mat[i][j] ){
auto [a, b] = pilha.top().second;
d[a][b] = i;
pilha.pop();
}
auto [a, b] = pilha.top().second;
u[i][j] = a;
pilha.push({ mat[i][j], make_pair( i, j ) });
}
for( int i = 0; i < n; i++ ) if( u[i][j] != -1 && mat[i][j] == mat[u[i][j]][j] ) d[u[i][j]][j] = i;
}
for( int i = 0; i < n; i++ ) for( int j = 0; j < m; j++ ){
linha[i].update( j, l[i][j], r[i][j], u[i][j], d[i][j] );
coluna[j].update( i, l[i][j], r[i][j], u[i][j], d[i][j] );
}
for( int i = 0; i < n; i++ ) for( int j = 0; j < m; j++ ){
if( l[i][j] != -1 && mat[i][j] == mat[i][l[i][j]] ) l[i][j] = l[i][l[i][j]];
if( u[i][j] != -1 && mat[i][j] == mat[u[i][j]][j] ) u[i][j] = u[u[i][j]][j];
}
for( int i = n - 1; i >= 0; i-- ) for( int j = m - 1; j >= 0; j-- ){
if( r[i][j] != m && mat[i][j] == mat[i][r[i][j]] ) r[i][j] = r[i][r[i][j]];
if( d[i][j] != n && mat[i][j] == mat[d[i][j]][j] ) d[i][j] = d[d[i][j]][j];
}
set<tuple<int, int, int, int>> s;
for( int i = 1; i < n - 1; i++ ) for( int j = 1; j < m - 1; j++ ){
if( l[i][j] == -1 || r[i][j] == m || u[i][j] == -1 || d[i][j] == n ) continue;
if( linha[u[i][j]].query( l[i][j] + 1, r[i][j] - 1, 2) < d[i][j] ) continue;
if( linha[d[i][j]].query( l[i][j] + 1, r[i][j] - 1, 0) > u[i][j] ) continue;
if( coluna[l[i][j]].query( u[i][j] + 1, d[i][j] - 1, 1) < r[i][j] ) continue;
if( coluna[r[i][j]].query( u[i][j] + 1, d[i][j] - 1, 3) > l[i][j] ) continue;
s.insert(make_tuple( l[i][j], r[i][j], u[i][j], d[i][j] ) );
}
return s.size();
}
