#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>stosy[2510];
int nast[2510][2510][4];
int maxi1(int war, int l, int r){
int res = -1;
for(int i=l;i<=r;i++)
res = max(res, nast[i][war][0]);
return res;
}
int mini1(int war, int l, int r){
int res = 2600;
for(int i=l;i<=r;i++)
res = min(res, nast[i][war][1]);
return res;
}
int maxi2(int war, int l, int r){
int res = -1;
for(int i=l;i<=r;i++)
res = max(res, nast[war][i][2]);
return res;
}
int mini2(int war, int l, int r){
int res = 2600;
for(int i=l;i<=r;i++)
res = min(res, nast[war][i][3]);
return res;
}
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size();
int m = a[0].size();
int i, j;
//poprzednie po x [0]
for(i=0;i<n;i++){
for(j=0;j<m;j++){
while(stosy[i].size() && stosy[i].back().first<=a[i][j])
stosy[i].pop_back();
if(stosy[i].size())
nast[i][j][0] = stosy[i].back().second;
else
nast[i][j][0] = -1;
stosy[i].push_back({a[i][j], j});
}
}
for(i=0;i<n;i++)
stosy[i].clear();
//nastepne po x [1]
for(i=0;i<n;i++){
for(j=m-1;j>=0;j--){
while(stosy[i].size() && stosy[i].back().first<=a[i][j])
stosy[i].pop_back();
if(stosy[i].size())
nast[i][j][1] = stosy[i].back().second;
else
nast[i][j][1] = m;
stosy[i].push_back({a[i][j], j});
}
}
for(i=0;i<n;i++)
stosy[i].clear();
//poprzednie po y [2]
for(i=0;i<m;i++){
for(j=0;j<n;j++){
while(stosy[i].size() && stosy[i].back().first<=a[j][i])
stosy[i].pop_back();
if(stosy[i].size())
nast[j][i][2] = stosy[i].back().second;
else
nast[j][i][2] = -1;
stosy[i].push_back({a[j][i], j});
}
}
for(i=0;i<m;i++)
stosy[i].clear();
//nastepne po y [3]
for(i=0;i<m;i++){
for(j = n-1;j>=0;j--){
while(stosy[i].size() && stosy[i].back().first<=a[j][i])
stosy[i].pop_back();
if(stosy[i].size())
nast[j][i][3] = stosy[i].back().second;
else
nast[j][i][3] = n;
stosy[i].push_back({a[j][i], j});
}
}
for(i=0;i<m;i++)
stosy[i].clear();
set<pair<pair<int,int>, pair<int,int>>>sett;
for(i=1;i<n-1;i++)
for(j=1;j<m-1;j++)
if(nast[i][j][0]!=-1 && nast[i][j][1]!=m && nast[i][j][2]!=-1 && nast[i][j][3]!=n){
sett.insert({{nast[i][j][0], nast[i][j][1]}, {nast[i][j][2], nast[i][j][3]}});
}
long long wynik = 0;
for(auto x: sett){
if(mini1(x.first.first, x.second.first+1, x.second.second-1)<x.first.second)continue;
if(maxi1(x.first.second, x.second.first+1, x.second.second-1)>x.first.first)continue;
if(mini2(x.second.first, x.first.first+1, x.first.second-1)<x.second.second)continue;
if(maxi2(x.second.second, x.first.first+1, x.first.second-1)>x.second.first)continue;
wynik++;
}
return wynik;
}
