#include "rect.h"
// In The Name Of Allah
#include <bits/stdc++.h>
#define ss second
#define ff first
#define use_fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ret(n) return cout << n, 0
#define se(n) cout << setprecision(n) << fixed
#define pb push_back
#define ll long long
using namespace std;
const long long N = 500, OO = 1e12 + 7, M = 1e9 + 7, M2 = 998244353, sq = 360, lg = 23;
typedef pair <ll, ll> pii;
ll bad[N][N][10], n, m, mn[N][N][N];
vector <vector <int> > a;
void get1(ll i) {
vector <ll> v;
for(ll j = 0; j < m; j++) {
while(v.size()) {
if(a[i][v[v.size() - 1]] < a[i][j])
v.pop_back();
else
break;
}
if(v.size())
bad[i][j][0] = v[v.size() - 1];
v.pb(j);
}
v.clear();
for(ll j = m - 1; j >= 0; j--) {
while(v.size()) {
if(a[i][v[v.size() - 1]] < a[i][j])
v.pop_back();
else
break;
}
if(v.size())
bad[i][j][1] = v[v.size() - 1];
else
bad[i][j][1] = m;
v.pb(j);
}
}
void get2(ll j) {
vector <ll> v;
for(ll i = 0; i < n; i++) {
while(v.size()) {
if(a[v[v.size() - 1]][j] < a[i][j])
v.pop_back();
else
break;
}
if(v.size())
bad[i][j][2] = v[v.size() - 1];
v.pb(i);
}
v.clear();
for(ll i = n - 1; i >= 0; i--) {
while(v.size()) {
if(a[v[v.size() - 1]][j] < a[i][j])
v.pop_back();
else
break;
}
if(v.size())
bad[i][j][3] = v[v.size() - 1];
else
bad[i][j][3] = n;
v.pb(i);
}
}
ll count_rectangles(vector<vector<int> > b) {
a = b;
n = (ll)a.size(), m = (ll)a[0].size();
for(ll i = 0; i < n; i++)
get1(i);
for(ll j = 0; j < m; j++)
get2(j);
for(ll k = 1; k < m; k++) {
for(ll i = 1; i < n; i++) {
mn[k][i][i] = bad[i][k][0];
for(ll j = i + 1; j < n - 1; j++)
mn[k][i][j] = max(mn[k][i][j - 1], bad[j][k][0]);
}
}
ll ans = 0;
for(ll k = 0; k < m - 2; k++) {
for(ll i = 1; i < n - 1; i++) {
ll mi = OO;
for(ll j = i; j < n - 1; j++) {
mi = min(mi, bad[j][k][1]);
ll mk = OO, ml = 0;
for(ll l = k + 1; l < m - 1; l++) {
mk = min(mk, bad[i - 1][l][3]);
ml = max(ml, bad[j + 1][l][2]);
ll mj = mn[l + 1][i][j];
if(mj >= k + 1 || mk <= j || ml >= i || mi <= l)
continue;
ans++;
}
}
}
}
return ans;
}
