#include "rect.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 1e9 + 10;
const int maxn = 2500 + 10;
const int logn = 13;
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( min( l, n.l ), max( r, n.r ), min( u, n.u ), max( d, n.d ) );
}
};
Node dp[logn][logn][maxn][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] = (( pilha.top().first == mat[i][j] ) ? l[a][b] : b );
pilha.push({ mat[i][j], make_pair( i, 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] = (( pilha.top().first == mat[i][j] ) ? u[a][b] : a );
pilha.push({ mat[i][j], make_pair( i, j ) });
}
}
for( int ki = 0; ki < logn; ki++ )
for( int kj = 0; kj < logn; kj++ )
for( int i = 0; i < n; i++ )
for( int j = 0; j < m; j++ ){
if( ki == 0 && kj == 0) dp[0][0][i][j] = Node( l[i][j], r[i][j], u[i][j], d[i][j] );
else if( ki == 0 ){
if( j + (1<<kj) <= m ) dp[ki][kj][i][j] = dp[ki][kj - 1][i][j] + dp[ki][kj - 1][i][j + (1<<(kj - 1))];
}
else if( i + (1<<ki) <= n ) dp[ki][kj][i][j] = dp[ki - 1][kj][i][j] + dp[ki - 1][kj][i + (1<<(ki - 1))][j];
}
auto query = [&]( int i1, int j1, int i2, int j2 ){
int ki = 31 - __builtin_clz(i2 - i1 + 1), kj = 31 - __builtin_clz(j2 - j1 + 1);
return dp[ki][kj][i1][j1] + dp[ki][kj][i1][j2 - (1<<kj) + 1] + dp[ki][kj][i2 - (1<<ki) + 1][j1] + dp[ki][kj][i2 - (1<<ki) + 1][j2 - (1<<kj) + 1];
};
ll resp = 0;
Node x = query( 1, 1, 1, 1 );
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;
Node x = query( u[i][j] + 1, l[i][j] + 1, d[i][j] - 1, r[i][j] - 1 );
if( x.u < u[i][j] || x.l < l[i][j] || x.d > d[i][j] || x.r > r[i][j] ) continue;
s.insert(make_tuple( l[i][j], r[i][j], u[i][j], d[i][j] ) );
}
if( resp > n*m ) return 0;
return s.size();
}
