#include "rect.h"
#include<bits/stdc++.h>
using namespace std;int maxst[2502][2502], maxdr[2502][2502], maxup[2502][2502], maxdwn[2502][2502];
int upleft[2502][2502], downleft[2502][2502], leftup[2502][2502], rightup[2502][2502];
vector<long long> v;
void check(int xa, int xb, int ya, int yb)
{
if(xb < xa || yb < ya)
return;
if(!((maxdr[xb][ya-1]-1 == yb && rightup[xb][ya-1] <= xa) || (maxst[xb][yb+1]+1 == ya && leftup[xb][yb+1] <= xa)))
return;
if(!((maxdwn[xa-1][yb]-1 == xb && downleft[xa-1][yb] <= ya) || (maxup[xb+1][yb]+1 == xa && upleft[xb+1][yb] <= ya)))
return;
v.push_back(((1LL * xa * 3010 + xb) * 3010 + ya) * 3010 + yb);
}
long long count_rectangles(vector<vector<int> > a)
{
int n = a.size();
int m = a[0].size();
long long ans = 0;
deque<int> d;
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
while(!d.empty() && a[i][j] > a[i][d.back()])
d.pop_back();
if(d.empty())
maxst[i][j] = -1;
else
maxst[i][j] = d.back();
d.push_back(j);
}
d.clear();
for(int j = m - 1; j >= 0; --j)
{
while(!d.empty() && a[i][j] > a[i][d.back()])
d.pop_back();
if(d.empty())
maxdr[i][j] = -1;
else
maxdr[i][j] = d.back();
d.push_back(j);
}
d.clear();
}
for(int i = 0; i < m; ++i)
{
for(int j = 0; j < n; ++j)
{
while(!d.empty() && a[j][i] > a[d.back()][i])
d.pop_back();
if(d.empty())
maxup[j][i] = -1;
else
maxup[j][i] = d.back();
d.push_back(j);
}
d.clear();
for(int j = n-1; j >= 0; --j)
{
while(!d.empty() && a[j][i] > a[d.back()][i])
d.pop_back();
if(d.empty())
maxdwn[j][i] = -1;
else
maxdwn[j][i] = d.back();
d.push_back(j);
}
d.clear();
}
for(int j = 0; j < m; ++j)
{
for(int i = 0; i < n; ++i)
{
if(maxup[i][j] != -1)
{
if(j > 0 && maxup[i][j] == maxup[i][j-1])
upleft[i][j] = upleft[i][j-1];
else
if(j > 0 && i == maxdwn[maxup[i][j]][j-1])
upleft[i][j] = downleft[maxup[i][j]][j-1];
else
upleft[i][j] = j;
}
if(maxdwn[i][j] != -1)
{
if(j > 0 && maxdwn[i][j] == maxdwn[i][j-1])
downleft[i][j] = downleft[i][j-1];
else
if(j > 0 && i == maxup[maxdwn[i][j]][j-1])
downleft[i][j] = upleft[maxdwn[i][j]][j-1];
else
downleft[i][j] = j;
}
}
}
for(int i = 0; i < n; ++i)
{
for(int j = 0; j < m; ++j)
{
if(maxst[i][j] != -1)
{
if(i > 0 && maxst[i][j] == maxst[i-1][j])
leftup[i][j] = leftup[i-1][j];
else
if(i > 0 && j == maxdr[i-1][maxst[i][j]])
leftup[i][j] = rightup[i-1][maxst[i][j]];
else
leftup[i][j] = i;
}
if(maxdr[i][j] != -1)
{
if(i > 0 && maxdr[i][j] == maxdr[i-1][j])
rightup[i][j] = rightup[i-1][j];
else
if(i > 0 && j == maxst[i-1][maxdr[i][j]])
rightup[i][j] = leftup[i-1][maxdr[i][j]];
else
rightup[i][j] = i;
}
}
}
for(int i = 1; i + 1 < n; ++i)
for(int j = 1; j + 1 < m; ++j)
{
if(maxup[i+1][j] != -1 && maxst[i][j+1] != -1)
check(maxup[i+1][j]+1, i, maxst[i][j+1]+1, j);
if(maxup[i+1][j] != -1 && maxdr[i][j-1] != -1)
check(maxup[i+1][j]+1, i, j, maxdr[i][j-1]-1);
if(maxdwn[i-1][j] != -1 && maxst[i][j+1] != -1)
check(i, maxdwn[i-1][j]-1, maxst[i][j+1]+1, j);
if(maxdwn[i-1][j] != -1 && maxdr[i][j-1] != -1)
check(i, maxdwn[i-1][j]-1, j, maxdr[i][j-1]-1);
if(maxdwn[i-1][j] != -1 && maxdr[maxdwn[i-1][j]-1][j-1] != -1)
check(i, maxdwn[i-1][j]-1, j, maxdr[maxdwn[i-1][j]-1][j-1]-1);
if(maxdwn[i-1][j] != -1 && maxst[maxdwn[i-1][j]-1][j+1] != -1)
check(i, maxdwn[i-1][j]-1, maxst[maxdwn[i-1][j]-1][j+1]+1, j);
}
sort(v.begin(), v.end());
v.resize(unique(v.begin(), v.end()) - v.begin());
return v.size();
}
