#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> lg{-1};
struct RMQ {
vector<vector<int>> sp;
void init (vector<int> &a) {
int n = a.size();
sp.resize(lg[n]+1, vector<int>(n));
sp[0] = a;
for (int i = 1; i < lg[n]+1; ++i) {
for (int j = 0; j < n - (1 << i) + 1; ++j) {
sp[i][j] = max(sp[i - 1][j], sp[i - 1][j + (1 << (i - 1))]);
}
}
}
int query (int l, int r) {
assert(r >= l);
int k = lg[r-l+1];
return max(sp[k][l], sp[k][r - (1 << k) + 1]);
}
};
long long count_rectangles(vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
for (int i = 1; i <= max(n, m); ++i) {
lg.push_back(lg.back()+!(i&(i-1)));
}
vector<RMQ> row(n), col(m);
for (int i = 0; i < n; ++i) {
row[i].init(a[i]);
}
for (int j = 0; j < m; ++j) {
vector<int> p;
for (int i = 0; i < n; ++i) {
p.push_back(a[i][j]);
}
col[j].init(p);
}
long long ans = 0;
for (int x = 1; x < n - 1; ++x) {
for (int y = 1; y < m - 1; ++y) {
for (int i = x; i < n - 1; ++i) {
if (a[i][y] >= a[i][y - 1] || a[i][y] >= a[x - 1][y]) {
break;
}
bool bad = 0;
for (int j = y; j < m - 1 && !bad; ++j) {
bool good = 1;
for (int l = x; l <= i && good; ++l) {
int mx = row[l].query(y, j);
good &= mx < a[l][j + 1] && mx < a[l][y - 1];
bad |= mx >= a[l][y - 1];
}
for (int r = y; r <= j && good; ++r) {
int mx = col[r].query(x, i);
good &= mx < a[i + 1][r] && mx < a[x - 1][r];
bad |= mx >= a[x - 1][r] || mx >= a[i + 1][r];
}
ans += good;
}
}
}
}
return ans;
}
