#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<short> b[2505][2505];
vector<short> c[2505][2505];
vector<pair<short,short>> d[2505][2505];
vector<pair<short,short>> e[2505][2505];
short lef[2505][2505];
short rig[2505][2505];
short up[2505][2505];
short down[2505][2505];
vector<short> v[2500*2500];
long long count_rectangles(std::vector<std::vector<int> > a) {
int n = a.size();
int m = a[0].size();
for(int i=1 ; i<n-1 ; i++){
stack<int> S;
for(int j=0 ; j<m ; j++){
bool flag = true;
while(!S.empty() && a[i][S.top()] <= a[i][j]){
int x = S.top();
if(x +1 <j && flag)
b[x+1][j-1].push_back(i);
if(a[i][S.top()]==a[i][j])flag=false;
S.pop();
}
if(!S.empty() ){
int x = S.top();
lef[i][j] = x;
if(x+1<j && flag)
b[x+1][j-1].push_back(i);
}
else{
lef[i][j]=-1;
}
S.push(j);
}
while(!S.empty())S.pop();
for(int j=m-1; j>=0 ; j--){
while(!S.empty() && a[i][S.top()] <= a[i][j]){
S.pop();
}
if(!S.empty() ){
int x = S.top();
rig[i][j] = x;
}
else{
rig[i][j]=-1;
}
S.push(j);
}
}
for(int i=1 ; i<m-1 ; i++){
stack<int> S;
for(int j=0 ; j<n ; j++){
bool flag = true;
while(!S.empty() && a[S.top()][i] <= a[j][i]){
int x = S.top();
if(x +1 <j && flag)
c[x+1][j-1].push_back(i);
if(a[S.top()][i]==a[j][i])flag=false;
S.pop();
}
if(!S.empty() ){
int x = S.top();
up[j][i]=x;
if(x+1<j && flag)
c[x+1][j-1].push_back(i);
}
else{
up[j][i]=-1;
}
S.push(j);
}
while(!S.empty())S.pop();
for(int j=n-1 ; j>=0 ; j--){
while(!S.empty() && a[S.top()][i] <= a[j][i]){
S.pop();
}
if(!S.empty() ){
int x = S.top();
down[j][i]=x;
}
else{
down[j][i]=-1;
}
S.push(j);
}
}
std::vector<vector<int>>().swap(a);
long long ans = 0;
for(int i=1 ; i<m ; i++){
for(int j=i ; j<m ; j++){
reverse(b[i][j].begin(),b[i][j].end());
int prv = -1;
int y;
for(auto x: b[i][j]){
if(x != prv-1){
if(prv>=0)
d[i][j].push_back({prv,y});
y=x;
}
prv=x;
}
if(prv>=0){
d[i][j].push_back({prv,y});
}
sort(d[i][j].begin(),d[i][j].end());
std::vector<short>().swap(b[i][j]);
}
}
for(int i=1 ; i<n ; i++){
for(int j=i ; j<n ; j++){
reverse(c[i][j].begin(),c[i][j].end());
int prv = -1;
int y;
for(auto x: c[i][j]){
if(x != prv-1){
if(prv>=0)
e[i][j].push_back({prv,y});
y=x;
}
prv=x;
}
if(prv>=0){
e[i][j].push_back({prv,y});
}
sort(e[i][j].begin(),e[i][j].end());
std::vector<short>().swap(c[i][j]);
}
}
int nn = 0;
for(int i = 1 ; i<n-1 ; i++){
for(int j=1 ; j<m-1 ; j++){
short x = lef[i][j];
short y = rig[i][j];
short z = up[i][j];
short w = down[i][j];
v[++nn]={x,y,z,w};
}
}
sort(v+1,v+nn+1);
for(int i=1 ; i<=nn ; i++){
if(v[i]==v[i-1])continue;
auto vv = v[i];
int x=vv[0];
int y = vv[1];
int z =vv[2];
int w = vv[3];
if(x==-1 ||y==-1 || z==-1 || w==-1)continue;
auto k = upper_bound(d[x+1][y-1].begin(),d[x+1][y-1].end(),(pair<short,short>){z+1,32767});
if(k== d[x+1][y-1].begin())continue;
if((--k)->second <w-1)continue;
auto t = upper_bound(e[z+1][w-1].begin(),e[z+1][w-1].end(),(pair<short,short>){x+1,32767});
if(t== e[z+1][w-1].begin())continue;
if((--t)->second <y-1)continue;
ans++;
}
return ans;
}
