#include <bits/stdc++.h>
using namespace std;
struct sparse_table{
int LOG;
vector<vector<int>> B;
sparse_table(){
}
sparse_table(vector<int> A){
int N = A.size();
LOG = 32 - __builtin_clz(N);
B = vector<vector<int>>(LOG, vector<int>(N, 0));
for (int i = 0; i < N; i++){
B[0][i] = A[i];
}
for (int i = 0; i < LOG - 1; i++){
B[i + 1] = B[i];
for (int j = 0; j < N - (1 << i); j++){
B[i + 1][j] = max(B[i + 1][j], B[i][j + (1 << i)]);
}
}
}
int range_max(int L, int R){
int d = R - L;
int p = 32 - __builtin_clz(d) - 1;
return max(B[p][L], B[p][R - (1 << p)]);
}
};
long long count_rectangles(vector<vector<int>> a){
int n = a.size();
int m = a[0].size();
assert(n <= 700 && m <= 700);
vector<sparse_table> STh(n);
for (int i = 0; i < n; i++){
STh[i] = sparse_table(a[i]);
}
vector<sparse_table> STv(m);
for (int i = 0; i < m; i++){
vector<int> b(n);
for (int j = 0; j < n; j++){
b[j] = a[j][i];
}
STv[i] = sparse_table(b);
}
set<tuple<int, int, int, int>> st;
for (int i = 1; i < n - 1; i++){
for (int j = 1; j < m - 1; j++){
int l = j;
while (l > 0){
if (a[i][l - 1] > a[i][j]){
break;
}
l--;
}
int r = j + 1;
while (r < m){
if (a[i][r] > a[i][j]){
break;
}
r++;
}
int u = i;
while (u > 0){
if (a[u - 1][j] > a[i][j]){
break;
}
u--;
}
int d = i + 1;
while (d < n){
if (a[d][j] > a[i][j]){
break;
}
d++;
}
if (l > 0 && r < m && u > 0 && d < n){
if (st.count(make_tuple(l, r, u, d)) == 0){
bool ok = true;
for (int x = u; x < d; x++){
if (STh[x].range_max(l, r) >= min(a[x][l - 1], a[x][r])){
ok = false;
}
}
for (int y = l; y < r; y++){
if (STv[y].range_max(u, d) >= min(a[u - 1][y], a[d][y])){
ok = false;
}
}
if (ok){
st.insert(make_tuple(l, r, u, d));
}
}
}
}
}
return st.size();
}
