#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 25e2;
const int inf = N + 1;
int nxt[4][N][N];
int prv[N][N];
int na[N][N];
int v2[N], cnt = 0;
int n, m;
vector <int> righ[N][N];
vector <int> down[N][N];
pair<int,int> rot(int x, int y, int deg, int n2 = n,int m2 = m){
for(int i = 0;i < deg;i++){
swap(x,y);
y = n2 - 1 - y;
swap(n2, m2);
}
return {x,y};
}
bool check(int x, int y, int x2, int y2){
//cout<<x<<' '<<y<<' '<<x2<<' '<<y2<<'\n';
if(x == 0 || y == 0 || x2 == n - 1 || y2 == m - 1)return 0;
for(int i = y;i <= y2;i++){
pair<int,int> f = rot(x - 1, i, 3);
pair<int,int> f2 = rot(x2 + 1, i, 1);
//cout<<f.first<<' '<<f.second<<' '<<f2.first<<' '<<f2.second<<' '<<nxt[3][f.first][f.second]<<' '<<nxt[1][f2.first][f2.second]<<' '<<rot(0, nxt[3][f.first][f.second], 1, m, n).first<<' '<<rot(0, nxt[1][f2.first][f2.second], 3, m, n).first<<'\n';
if(rot(0, nxt[3][f.first][f.second], 1, m, n).first <= x2)return 0;
if(rot(0, nxt[1][f2.first][f2.second], 3, m, n).first >= x)return 0;
}
//cout<<"??\n";
for(int i = x;i <= x2;i++){
pair<int,int> f = rot(i, y - 1, 0);
pair<int,int> f2 = rot(i, y2 + 1, 2);
//cout<<f2.first<<' '<<f2.second<<' '<<nxt[2][f2.first][f2.second]<<' '<<rot(0, nxt[2][f2.first][f2.second], 2).second<<'\n';
if(nxt[0][f.first][f.second] <= y2)return 0;
if(rot(0, nxt[2][f2.first][f2.second], 2).second >= y)return 0;
}
return 1;
}
long long count_rectangles(std::vector<std::vector<int>> a) {
auto check2 = [&](int x, int y, int x2, int y2) -> bool{
if(x == 0 || y == 0 || x2 == n - 1 || y2 == m - 1)return 0;
for(int i = x;i <= x2;i++){
for(int j = y;j <= y2;j++){
if(a[i][j] >= a[x - 1][j])return 0;
if(a[i][j] >= a[x2 + 1][j])return 0;
if(a[i][j] >= a[i][y - 1])return 0;
if(a[i][j] >= a[i][y2 + 1])return 0;
}
}
return 1;
};
auto rightadd = [&](int x, int y, int p) -> void{
if(0 <= x && x < n && 0 <= y && y < m && 0 <= p && p < m && y <= p){
righ[x][y].push_back(p);
}
};
n = a.size();
m = a[0].size();
int n2 = n;
int m2 = m;
for(int deg = 0;deg < 4;deg++){
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
pair <int,int> f = rot(i, j, deg);
na[f.first][f.second] = a[i][j];
nxt[deg][f.first][f.second] = inf;
}
}
for(int i = 0;i < n2;i++){
cnt = 0;
for(int j = 0;j < m2;j++){
int nr = na[i][j];
while(cnt > 0 && na[i][v2[cnt - 1]] <= na[i][j]){
nxt[deg][i][v2[cnt - 1]] = j;
cnt--;
}
v2[cnt++] = j;
}
}
swap(n2,m2);
}
int ans = 0;
/*for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
for(int k = i;k < n;k++){
for(int p = j;p < m;p++){
if(check(i,j,k,p)){
ans++;
}
}
}
}
}*/
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
pair<int,int> t = rot(i,j,2);
rightadd(i, j, nxt[0][i][j - 1] - 1);
rightadd(i, rot(t.first, nxt[2][t.first][t.second], 2).second + 1, j - 1);
//righ[i][j].push_back(nxt[0][i][j - 1]);
//righ[i][rot(t.first, nxt[2][t.first][t.second], 2).second + 1].push_back(j);
}
}
for(int i = 1;i < n - 1;i++){
for(int j = 1;j < m - 1;j++){
///n^2 checks max?
sort(righ[i][j].begin(),righ[i][j].end());
righ[i][j].erase(unique(righ[i][j].begin(),righ[i][j].end()),righ[i][j].end());
for(int l = i;l < n - 1;l++){
for(auto k:righ[i][j]){
assert(j <= k && k <= m - 1);
//cout<<i<<' '<<j<<' '<<l<<' '<<k<<'\n';
if(check(i,j,l,k)){
ans++;
}
}
}
}
}
return ans;
}
