#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> a;
namespace sub4{
const int N=700;
bitset<N> b[N][N], bs[N], c[N][N], msk[N][N];
bool check(){
return n<=700 && m<=700;
}
long long solve(){
for (int i=0; i<m; ++i) for (int j=i; j<m; ++j){
msk[i][j]=msk[i][j-1];
msk[i][j].set(j);
}
for (int i=0; i<n; ++i){
for (int l=0; l<m; ++l){
int mx=0;
for (int r=l+2; r<m; ++r){
mx=max(mx, a[i][r-1]);
if (a[i][l]>mx && a[i][r]>mx) b[i][l].set(r);
}
}
}
for (int i=0; i<m; ++i){
for (int l=0; l<n; ++l){
int mx=0;
for (int r=l+2; r<n; ++r){
mx=max(mx, a[r-1][i]);
if (a[l][i]>mx && a[r][i]>mx) c[i][l].set(r);
}
}
}
long long ans=0;
for (int i=0; i<n; ++i){
for (int j=0; j<m; ++j) bs[j].set();
for (int j=i+2; j<n; ++j){
for (int k=m-1, nxt=m-1; k>=0; --k){
bs[k]&=b[j-1][k];
if (k+2<=nxt) ans+=(bs[k]&msk[k+2][nxt]).count();
if (!c[k][i].test(j)) nxt=k;
}
}
}
return ans;
}
}
namespace sub5{
const int N=2500;
bitset<3> b[N][3], bs[3];
bitset<N> c[3][N];
bitset<3> msk[3][3];
bool check(){
return n<=3;
}
long long solve(){
vector<vector<int>> aa(m, vector<int>(n));
for (int i=0; i<n; ++i) for (int j=0; j<m; ++j) aa[j][i]=a[i][j];
swap(n, m);
aa.swap(a);
for (int i=0; i<m; ++i) for (int j=i; j<m; ++j){
msk[i][j]=msk[i][j-1];
msk[i][j].set(j);
}
for (int i=0; i<n; ++i){
for (int l=0; l<m; ++l){
int mx=0;
for (int r=l+2; r<m; ++r){
mx=max(mx, a[i][r-1]);
if (a[i][l]>mx && a[i][r]>mx) b[i][l].set(r);
}
}
}
for (int i=0; i<m; ++i){
for (int l=0; l<n; ++l){
int mx=0;
for (int r=l+2; r<n; ++r){
mx=max(mx, a[r-1][i]);
if (a[l][i]>mx && a[r][i]>mx) c[i][l].set(r);
}
}
}
long long ans=0;
for (int i=0; i<n; ++i){
for (int j=0; j<m; ++j) bs[j].set();
for (int j=i+2; j<n; ++j){
for (int k=m-1, nxt=m-1; k>=0; --k){
bs[k]&=b[j-1][k];
if (k+2<=nxt) ans+=(bs[k]&msk[k+2][nxt]).count();
if (!c[k][i].test(j)) nxt=k;
}
}
}
return ans;
}
}
long long count_rectangles(vector<vector<int>> _a){
a=_a;
n=a.size(), m=a[0].size();
if (sub4::check()) return sub4::solve();
if (sub5::check()) return sub5::solve();
return 0;
}
