#include <bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;
const int MAXN = 2510;
const int INF = 1000000010;
class SegmentTree
{
public:
int getLeft(int node) { return 2*node; }
int getRight(int node) { return 2*node + 1; }
void update(int node, int l, int r, int i, int v)
{
if( i < l || r < i ) return;
if( l == r )
{
mx[ node ] = v;
return;
}
int m = ( l + r )/2;
update( getLeft(node) , l , m , i , v );
update( getRight(node) , m + 1 , r , i , v );
mx[node] = max( mx[ getLeft(node) ] , mx[ getRight(node) ] );
}
int query(int node, int l, int r, int i, int j)
{
if( j < l || r < i ) return -INF;
if( i <= l && r <= j ) return mx[node];
int m = ( l + r )/2;
int mxLeft = query( getLeft(node) , l , m , i , j );
int mxRight = query( getRight(node) , m + 1 , r , i , j );
return max( mxLeft , mxRight );
}
SegmentTree()
{
for(int i = 0 ; i < 4*MAXN ; i++)
mx[i] = -INF;
}
private:
int mx[4*MAXN];
};
int n, m;
int v[MAXN][MAXN];
int L[MAXN][MAXN];
int R[MAXN][MAXN][2];
int up[MAXN][MAXN];
int down[MAXN][MAXN][2];
SegmentTree mnR[MAXN];
SegmentTree mxL[MAXN];
SegmentTree mxUp[MAXN];
SegmentTree mnDown[MAXN];
void makeHistogram()
{
for(int i = 1 ; i <= n ; i++)
{
v[i][0] = v[i][m + 1] = INF;
for(int j = 1 ; j <= m ; j++)
{
int cur = j - 1;
while( v[i][cur] < v[i][j] ) cur = L[i][cur];
L[i][j] = cur;
}
for(int j = m ; j > 0 ; j--)
{
int cur = j + 1;
while( v[i][cur] <= v[i][j] ) cur = R[i][cur][0];
R[i][j][0] = cur;
}
for(int j = m ; j > 0 ; j--)
{
int cur = j + 1;
while( v[i][cur] < v[i][j] ) cur = R[i][cur][1];
R[i][j][1] = cur;
}
}
for(int j = 1 ; j <= m ; j++)
{
v[0][j] = v[n + 1][j] = INF;
for(int i = 1 ; i <= n ; i++)
{
int cur = i - 1;
while( v[cur][j] < v[i][j] ) cur = up[cur][j];
up[i][j] = cur;
}
for(int i = n ; i > 0 ; i--)
{
int cur = i + 1;
while( v[cur][j] <= v[i][j] ) cur = down[cur][j][0];
down[i][j][0] = cur;
}
for(int i = n ; i > 0 ; i--)
{
int cur = i + 1;
while( v[cur][j] < v[i][j] ) cur = down[cur][j][1];
down[i][j][1] = cur;
}
}
}
void preProcess()
{
for(int i = 2 ; i < n ; i++)
{
for(int j = 2 ; j < m ; j++)
{
mnR[j].update( 1 , 1 , n , i , -R[i][j][1] );
mxL[j].update( 1 , 1 , n , i , L[i][j] );
//printf("j = %d i = %d %d\n",i,j,-R[i][j][1]);
mxUp[i].update( 1 , 1 , m , j , up[i][j] );
mnDown[i].update( 1 , 1 , m , j , -down[i][j][1] );
}
}
}
bool isAnswer(int x1, int y1, int x2, int y2)
{
int mnRight = -mnR[y1 - 1].query( 1 , 1 , n , x1 , x2 );
int mxLeft = mxL[y2 + 1].query( 1 , 1 , n , x1 , x2 );
int mxCurUp = mxUp[x2 + 1].query( 1 , 1 , m , y1 , y2 );
int mnCurDown = -mnDown[x1 - 1].query( 1 , 1 , m , y1 , y2 );
//printf("==== %d %d %d %d\n",x1,y1,x2,y2);
//printf("........ %d %d %d %d\n",mnRight,mxLeft,mxCurUp,mnCurDown);
if( mnRight <= y2 ) return false;
if( y1 <= mxLeft ) return false;
//printf("oi\n");
if( mnCurDown <= x2 ) return false;
if( x1 <= mxCurUp ) return false;
//printf("pa\n");
return true;
}
long long count_rectangles(vector< vector<int> > a) //Grids pequenos
{
n = a.size();
m = a[0].size();
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < m ; j++)
v[i + 1][j + 1] = a[i][j];
makeHistogram();
vector< pair<pii,pii> > aux;
vector< pair<pii,pii> > rect;
for(int i = 2 ; i < n ; i++)
{
for(int j = 2 ; j < m ; j++)
{
if( L[i][j] == 0 ) continue;
if( R[i][j][0] == m + 1 ) continue;
if( up[i][j] == 0 ) continue;
if( down[i][j][0] == n + 1 ) continue;
pii dY = { L[i][j] + 1 , R[i][j][0] - 1 };
pii dX = { up[i][j] + 1 , down[i][j][0] - 1 };
aux.push_back( { dX , dY } );
}
}
preProcess();
sort( aux.begin() , aux.end() );
for(int i = 0 ; i < aux.size() ; i++)
if( i == 0 || aux[i] != aux[i - 1] ) rect.push_back( { aux[i] } );
lli ans = 0;
for(int i = 0 ; i < rect.size() ; i++)
{
int x1 = rect[i].first.first;
int x2 = rect[i].first.second;
int y1 = rect[i].second.first;
int y2 = rect[i].second.second;
if( isAnswer( x1 , y1 , x2 , y2 ) ) ans++;
}
return ans;
}
