#include <bits/stdc++.h>
#include "rect.h"
#define sz(x) (int)x.size()
#define mkt make_tuple
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define eb emplace_back
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define debug printf
#define all(x) x.begin(),x.end()
const int MAXN = 2510 ;
using namespace std ;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
int N , M ;
void solve( vector< vector<int > > &grid, vector< vector< vector<pii> > > &toPut )
{
int tamLinha = sz( grid[0] ) ;
vector<int> esq(tamLinha) , dir(tamLinha) , getFreq( tamLinha ) , lastVisit(tamLinha) ;
for(int i = 1 ; i < sz(grid) - 1 ; i++ )
{
for(int j = tamLinha - 1 ; j >= 0 ; j-- )
esq[j] = dir[j] = -1 ;
set<pii> s ;
for(int j = tamLinha - 2; j >= 0 ; j-- )
{
int x = j+1 ;
while( x != -1 && grid[i][x]<= grid[i][j] )
x = dir[x] ;
dir[j] = x ;
}
for(int j = 1 ; j < tamLinha ; j++ )
{
int x = j-1 ;
while(x != -1 && grid[i][x] <= grid[i][j] )
x = esq[x] ;
esq[j] = x ;
}
lp(j,1,tamLinha-1)
if( esq[j] != -1 && dir[j] != -1 && s.find(mk( esq[j] , dir[j] )) == s.end() )
{
toPut[ i ][ esq[j]+1 ].emplace_back( mk(dir[j]-1 , i) ) ;
s.insert( mk(esq[j] , dir[j]) ) ;
}
}
for(int j = 1 ; j < tamLinha ; j++ )
{
lp(i,0,tamLinha) getFreq[i] = lastVisit[i] = -1 ;
for(int i = sz(grid) - 2 ; i >= 1 ; i-- )
for(auto &e : toPut[i][j] )
{
if( lastVisit[e.ff] != i+1 ) getFreq[e.ff] = i ;
e.ss = getFreq[e.ff] ;
lastVisit[e.ff] = i ;
}
}
}
ll count_rectangles( vector<vector<int> > mat )
{
N = sz(mat) ;
M = sz( mat[0] ) ;
vector< vector<int> > gridCerto , gridRota ;
vector< vector< vector<pii> > > auxCerto, auxRota ;
lp(i,0,N)
{
gridCerto.emplace_back(*(new vector<int>)) ;
auxCerto.emplace_back(*(new vector< vector<pii> >)) ;
lp(j,0,M)
{
gridCerto[i].emplace_back( mat[i][j] ) ;
auxCerto[i].emplace_back( *(new vector<pii>) ) ;
}
}
lp(i,0,M)
{
gridRota.emplace_back( *(new vector<int>) ) ;
auxRota.emplace_back(*(new vector< vector<pii> >)) ;
lp(j,0,N)
{
gridRota[i].emplace_back( mat[j][i] ) ;
auxRota[i].emplace_back( *(new vector<pii>) ) ;
}
}
solve(gridCerto, auxCerto ) ;
solve( gridRota, auxRota );
/* lp(i,1,N-1)
{
lp(j,1,M-1)
{
printf("Na casinha %d %d -> " , i , j ) ;
for(auto e : auxCerto[i][j] ) printf("%d %d, " , e.ff, e.ss ) ;
printf("\n") ;
}
} */
ll ans = 0LL ;
lp(i,1,N-1)
lp(j,1,M-1)
{
sort( all(auxCerto[i][j]) ) ;
sort( all(auxRota[j][i]) , [&](pii i, pii j) { return i.ss < j.ss ; }) ;
ordered_set o_set ;
lp(e,0, sz(auxRota[j][i]) ) o_set.insert( mk(auxRota[j][i][e].ff, e) ) ;
int ptr = 0 ;
for(auto e : auxCerto[i][j] )
{
while( ptr < sz( auxRota[j][i] ) && auxRota[j][i][ptr].ss < e.ff )
{
o_set.erase( o_set.find( mk(auxRota[j][i][ptr].ff, ptr) ) ) ;
ptr++ ;
}
ans += (ll)( o_set.order_of_key( mk( e.ss+1, -1 ) ) ) ;
}
}
return ans ;
}
