#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll , ll> ii;
#define ff first
#define ss second
#define pb push_back
#define in insert
const ll N = 703;
ll R_mx[N][N][11], C_mx[N][N][11];
long long count_rectangles(std::vector<std::vector<int> > a) {
ll n = a.size();
ll m = a[0].size();
if(min(n, m) < 3) return 0;
n -= 2; m -= 2;
memset(R_mx, 0, sizeof(R_mx));
memset(C_mx, 0, sizeof(C_mx));
for(ll R = 1; R <= n; R++){
// len = 1
for(ll i = 1; i <= m; i++){
R_mx[R][i][0] = a[R][i];
}
for(ll i = m; i >= 1; i--){
for(ll j = 1; j < 11; j++){
R_mx[R][i][j] = R_mx[R][i][j - 1];
if(i + (1 << (j - 1)) <= m){
R_mx[R][i][j] = max(R_mx[R][i][j], R_mx[R][i + (1 << (j - 1))][j - 1]);
}
}
}
}
for(ll C = 1; C <= m; C++){
// len = 1
for(ll i = 1; i <= n; i++){
C_mx[C][i][0] = a[i][C];
}
for(ll i = n; i >= 1; i--){
for(ll j = 1; j < 11; j++){
C_mx[C][i][j] = C_mx[C][i][j - 1];
if(i + (1 << (j - 1)) <= n){
C_mx[C][i][j] = max(C_mx[C][i][j], C_mx[C][i + (1 << (j - 1))][j - 1]);
}
}
}
}
/* for(ll i = 1; i <= m; i++){
for(ll j = 1; j <= n; j++){
cout << j << ' ' << i << ' ' << 0 << ' ' << C_mx[j][i][0] << '\n';
}
}*/
ll ans = 0;
for(ll r1 = 1; r1 <= n; r1++){
for(ll c1 = 1; c1 <= m; c1++){
for(ll r2 = r1; r2 <= n; r2++){
for(ll c2 = c1; c2 <= m; c2++){
// (r1, c1) --- (r2, c2)
bool ok1 = 1;
ll LG = log2(c2 - c1 + 1);
for(ll i = r1; i <= r2; i++){
if(min(a[i][c1-1], a[i][c2+1]) <= max(R_mx[i][c1][LG] , R_mx[i][c2 - (1 << LG) + 1][LG] )){
ok1 = 0;
break;
}
}
LG = log2(r2 - r1 + 1);
if(min(a[r1-1][c2], a[r2+1][c2]) <= max(C_mx[c2][r1][LG], C_mx[c2][r2 - (1 << LG) + 1][LG])) break;
if(ok1) ans++;
}
}
}
}
return ans;
}
