#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define what_is(a) cerr << #a << " is " << a << endl
#define checker(a) cerr << "checker reached " << a << endl
#define cout cerr
const int MAXN = 1e3+1;
const int K = 25;
//sparce table
struct sparce{
int log[MAXN+1];
int st[MAXN][K + 1];
int N;
void init(vector<int>& array){
N = array.size();
log[1] = 0;
for (int i = 2; i <= MAXN; i++)
log[i] = log[i/2] + 1;
for (int i = 0; i < N; i++)
st[i][0] = array[i];
for (int j = 1; j <= K; j++)
for (int i = 0; i + (1 << j) <= N; i++)
st[i][j] = max(st[i][j-1], st[i + (1 << (j - 1))][j - 1]);
}
int getMax(int L,int R){
int j = log[R - L + 1];
return max(st[L][j], st[R - (1 << j) + 1][j]);
}
};
sparce rows[1000],cols[1000];
vector<vector<signed>> a;
bool check(int r1,int c1,int r2,int c2){
for(int i=r1;i<=r2;i++){
int r = rows[i].getMax(c1,c2);
if(r>=a[i][c1-1]||r>=a[i][c2+1])return false;
}
for(int j=c1;j<=c2;j++){
int r = cols[j].getMax(r1,r2);
if(r>=a[r1-1][j]||r>=a[r2+1][j])return false;
}
return true;
}
long long count_rectangles(std::vector<std::vector<signed> > A) {
a = A;
int n = a.size(),m=a[0].size();
assert(n<=200);
vector<int> vec(m);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++)
vec[j] = a[i][j];
rows[i].init(vec);
}
vector<int> vec2(n);
for(int j=0;j<m;j++){
for(int i=0;i<n;i++)
vec2[i]=a[i][j];
cols[j].init(vec2);
}
int ans = 0;
for(int r1=1;r1<n-1;r1++)
for(int c1=1;c1<m-1;c1++)
for(int r2=r1;r2<n-1;r2++)
for(int c2=c1;c2<m-1;c2++){
ans += check(r1,c1,r2,c2);
}
return ans;
}
