#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;
#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)
#define len(x) ((int)x.size())
long long count_rectangles(std::vector<std::vector<int> > a) {
long long ans=0;
// vert pairs
vector<ii> vert[2500], hor[2500];
FORi(i,1,len(a[0])-1){
// i-th column
FOR(j, len(a)-1){
int maxa = a[j+1][i];
FORi(k,j+2, len(a)){
if(maxa>=a[j][i]) break;
if(maxa>=a[k][i]) continue;
vert[i].push_back({j,k});
maxa = max(maxa, a[k][i]);
}
}
}
// horizontal pairs
FORi(i,1,len(a)-1){
// i-th column
FOR(j,len(a[0])-1){
int maxa = a[i][j+1];
FORi(k,j+2, len(a[0])){
if(maxa>=a[i][j]) break;
if(maxa>=a[i][k]) continue;
hor[i].push_back({j,k});
maxa = max(maxa, a[i][k]);
}
}
}
#ifdef LOCAL
FOR(i,len(a[0])) FOA(v, vert[i]) cout<<i<<" "<<v.F<<" "<<v.S<<endl;
cout<<endl;
FOR(i,len(a)) FOA(v, hor[i]) cout<<i<<" "<<v.F<<" "<<v.S<<endl;
cout<<endl;
#endif
// find sides
vector<pair<ii, ii> > horside;
FOR(i, len(a)){
FOA(v, hor[i]){
int last_ok = i;
FORi(j, i, len(a)){
if(binary_search(hor[j].begin(), hor[j].end(), v)) last_ok = j;
else break;
}
horside.push_back({{v.F+1, v.S-1}, {i, last_ok}});
}
}
sort(horside.begin(), horside.end());
FOR(i, len(a[0])){
FOA(v, vert[i]){
FORi(j, i, len(a[0])){
if(binary_search(vert[j].begin(), vert[j].end(), v)){
auto targ = mp(mp((ll)i,(ll)j), mp(v.F+1,v.S-1));
auto it = lower_bound(horside.begin(), horside.end(), targ);
if(it==horside.end()) continue;
if((*it).F==targ.F && (*it).S.F==targ.S.F) ans++;
}
else break;
}
}
}
// consider each starting point
return ans;
}
