#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pb push_back
#define REP(i,n) for(int i = 0; i < n; i++)
#define FOR(i,a,b) for(int i = a; i < b; i++)
#define FORD(i,a,b) for(int i = a; i >= b; i --)
#define pii pair<int,int>
#define F first
#define S second
#define all(v) v.begin(),v.end()
#define SZ(v) (int)v.size()
const ll MX = 2505;
ll ans = 0;
int n,m;
int gl[MX][MX],gr[MX][MX],gu[MX][MX],gd[MX][MX];
// int glfuck[MX][MX],grfuck[MX][MX],gufuck[MX][MX],gdfuck[MX][MX];
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
void check_rectangle(int x1,int y1,int x2,int y2){
FOR(i,x1,x2+1){
if(gr[i][y1-1] != y2+1 and gl[i][y2+1] != y1-1) return;
}
FOR(j,y1,y2+1){
if(gd[x1-1][j] != x2+1 and gu[x2+1][j] != x1-1) return;
}
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << "\n";
ans++;
}
ll count_rectangles(vector<vi> a){
n = a.size();
m = a[0].size();
if(n <= 2 or m <= 2) return 0;
FORD(i,n-1,0){
stack<int> st;
REP(j,m){
gl[i][j] = gr[i][j] = gu[i][j] = gd[i][j] = -1;
}
REP(j,m){
while(st.size() and a[i][st.top()] <= a[i][j]){
if(j-1 > st.top()) gr[i][st.top()] = j;
st.pop();
}
st.push(j);
}
while(!st.empty()) st.pop();
FORD(j,m-1,0){
while(st.size() and a[i][st.top()] < a[i][j]){
if(j+1 < st.top()) gl[i][st.top()] = j;
st.pop();
}
st.push(j);
}
}
FORD(j,m-1,0){
stack<int> st;
REP(i,n){
while(st.size() and a[st.top()][j] <= a[i][j]){
if(i-1 > st.top()) gd[st.top()][j] = i;
st.pop();
}
st.push(i);
}
while(!st.empty()) st.pop();
FORD(i,n-1,0){
while(st.size() and a[st.top()][j] < a[i][j]){
if(i+1 < st.top()) gu[st.top()][j] = i;
st.pop();
}
st.push(i);
}
}
vector<ll> bruh;
FOR(i,1,n-1){
FOR(j,1,m-1){
// // topleft
// if(gr[i][j-1] != -1 and gd[i-1][j] != -1){
// bruh.pb((i)*MX*MX*MX+(j)*MX*MX+(gd[i-1][j]-1)*MX+gr[i][j-1]-1);
// }
// // topright
// if(gl[i][j+1] != -1 and gd[i-1][j] != -1){
// bruh.pb((i)*MX*MX*MX+(gl[i][j+1]+1)*MX*MX+(gd[i-1][j]-1)*MX+j);
// }
// // bottomleft
// if(gr[i][j-1] != -1 and gu[i+1][j] != -1){
// bruh.pb((gu[i+1][j]+1)*MX*MX*MX+(j)*MX*MX+(i)*MX+gr[i][j-1]-1);
// }
// // bottomright
// if(gl[i][j+1] != -1 and gu[i+1][j] != -1){
// bruh.pb((gu[i+1][j]+1)*MX*MX*MX+(gl[i][j+1]+1)*MX*MX+(i)*MX+j);
// }
// // clockwise
// if(gr[i][j-1] != -1 and gd[i-1][gr[i][j-1]-1] != -1){
// bruh.pb((i)*MX*MX*MX+(j)*MX*MX+(gd[i-1][gr[i][j-1]-1]-1)*MX+gr[i][j-1]-1);
// }
// // anti-clockwise
// if(gl[i][j+1] != -1 and gd[i-1][gl[i][j+1]+1] != -1){
// bruh.pb((i)*MX*MX*MX+(gl[i][j+1]+1)*MX*MX+(gd[i-1][gl[i][j+1]+1]-1)*MX+j);
// }
FOR(k,i,n-1){
FOR(l,j,m-1){
check_rectangle(i,j,k,l);
}
}
}
}
// sort(all(bruh));
// REP(i,SZ(bruh)){
// if(i == 0 or bruh[i] != bruh[i-1]){
// check_rectangle(bruh[i]/(MX*MX*MX),(bruh[i]/(MX*MX))%MX,(bruh[i]/MX)%MX,bruh[i]%MX);
// }
// }
return ans;
}
