#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 na[N][N];
int v2[N], cnt = 0;
int n, m;
int rightspec[N][N];
int leftspec[N][N];
int downspec[N][N];
int upspec[N][N];
vector <array<int,4>> cand;
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};
}
pair<int,int> get(int x, int y, int dir){
if(dir == 0){
return {x, nxt[0][x][y]};
}else if(dir == 1){
pair<int,int> f2 = rot(x, y, 1);
return {rot(0, nxt[1][f2.first][f2.second], 3, m, n).first, y};
}else if(dir == 2){
pair<int,int> f2 = rot(x, y, 2);
return {x, rot(0, nxt[2][f2.first][f2.second], 2).second};
}else{
pair<int,int> f2 = rot(x, y, 3);
return {rot(0, nxt[3][f2.first][f2.second], 1, m, n).first, y};
}
}
bool check(int x, int y, int x2, int y2){
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);
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;
}
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);
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;
}
bool checkfast(int x, int y, int x2, int y2){
if(x <= 0 || y <= 0 || x2 >= n - 1 || y2 >= m - 1 || x > x2 || y > y2)return 0;
//cout<<x<<' '<<y<<' '<<x2<<' '<<y2<<'\n';
if(!((upspec[x2 + 1][y2] <= y && get(x2 + 1,y2,1).first == x - 1) || (downspec[x - 1][y2] <= y && get(x - 1, y2, 3).first == x2 + 1)))return 0;
if(!((rightspec[x2][y - 1] <= x && get(x2,y - 1,0).second == y2 + 1) || (leftspec[x2][y2 + 1] <= x && get(x2, y2 + 1, 2).second == y - 1)))return 0;
return 1;
}
long long count_rectangles(std::vector<std::vector<int>> a) {
auto checkslow = [&](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;
};
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);
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
rightspec[i][j] = i;
leftspec[i][j] = i;
if(i){
int r = get(i, j, 0).second;
if(r == get(i - 1, j, 0).second){
rightspec[i][j] = rightspec[i - 1][j];
}else if(j == get(i - 1, r, 2).second){
rightspec[i][j] = leftspec[i - 1][r];
}
int l = get(i, j, 2).second;
if(l == get(i - 1, j, 2).second){
leftspec[i][j] = leftspec[i - 1][j];
}else if(j == get(i - 1, l, 0).second){
leftspec[i][j] = rightspec[i - 1][l];
}
}
}
}
for(int j = 0;j < m;j++){
for(int i = 0;i < n;i++){
upspec[i][j] = j;
downspec[i][j] = j;
if(j){
int u = get(i, j, 1).first;
if(u == get(i, j - 1, 1).first){
upspec[i][j] = upspec[i][j - 1];
}else if(i == get(u, j - 1, 3).first){
upspec[i][j] = downspec[u][j - 1];
}
int d = get(i, j, 3).first;
if(d == get(i, j - 1, 3).first){
downspec[i][j] = downspec[i][j - 1];
}else if(i == get(d, j - 1, 1).first){
downspec[i][j] = upspec[d][j - 1];
}
}
}
}
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
int r = get(i, j, 0).second;
if(j + 1 <= r - 1 && r < m){
if(i){
cand.push_back({i, j + 1, get(i - 1, j + 1, 3).first - 1, r - 1});
cand.push_back({i, j + 1, get(i - 1, r - 1, 3).first - 1, r - 1});
}
if(i < n - 1){
cand.push_back({get(i + 1, j + 1, 1).first + 1, j + 1, i, r - 1});
cand.push_back({get(i + 1, r - 1, 1).first + 1, j + 1, i, r - 1});
}
}
int l = get(i, j, 2).second;
if(l + 1 <= j - 1 && l >= 0){
if(i){
cand.push_back({i, l + 1, get(i - 1, l + 1, 3).first - 1, j - 1});
cand.push_back({i, l + 1, get(i - 1, j - 1, 3).first - 1, j - 1});
}
if(i < n - 1){
cand.push_back({get(i + 1, l + 1, 1).first + 1, l + 1, i, j - 1});
cand.push_back({get(i + 1, j - 1, 1).first + 1, l + 1, i, j - 1});
}
}
}
}
/*
for(int i = 0;i < n;i++){
for(int j = 0;j < m;j++){
cand.push_back({i,j,i,j});
}
}
*/
sort(cand.begin(),cand.end());
int ans = 0;
for(int i = 0;i < cand.size();i++){
if(i && cand[i] == cand[i - 1])continue;
if(checkfast(cand[i][0], cand[i][1], cand[i][2], cand[i][3]))ans++;
}
return ans;
}
