#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;
int n, m;
int L[MAXN];
int R[MAXN];
int v[MAXN][MAXN];
void makeHistogram()
{
int i = 2;
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[cur];
L[j] = cur;
}
for(int j = m ; j > 0 ; j--)
{
int cur = j + 1;
while( v[i][cur] <= v[i][j] ) cur = R[cur];
R[j] = cur;
}
}
long long count_rectangles(vector< vector<int> > a) //Grids pequenos
{
n = a.size();
m = a[0].size();
if( n <= 2 ) return 0;
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < m ; j++)
v[i + 1][j + 1] = a[i][j];
makeHistogram();
int ans = 0;
for(int i = 1 ; i <= m ; i++)
{
bool possible = true;
if( L[i] == 0 || R[i] == m + 1 ) continue;
for(int j = L[i] + 1 ; j < R[i] ; j++)
possible = possible && ( v[2][j] < v[1][j] && v[2][j] < v[3][j] );
if( possible ) ans++;
}
return ans;
}
