#include<bits/stdc++.h>
#include "rect.h"
using namespace std;
typedef long long llint;
typedef pair <int, int> pi;
const int MAXN = 705;
const int INF = 1000000007;
int n, m, curr, sol;
int a[MAXN][MAXN], mx[MAXN];
int lef[MAXN][MAXN], rig[MAXN][MAXN];
vector <pi> v[MAXN];
int ok[MAXN], cnt[MAXN][MAXN];
void precompute_row (int r) {
vector <int> st;
for (int c = 0; c < m; c++) {
while (!st.empty() && a[r][st.back()] < a[r][c]) st.pop_back();
lef[r][c] = (st.empty() ? -1 : st.back());
st.push_back(c);
if (lef[r][c] != -1 && lef[r][c] != c - 1) v[r].push_back({lef[r][c] + 1, c - 1});
}
st.clear();
for (int c = m - 1; c >= 0; c--) {
while (!st.empty() && a[r][st.back()] < a[r][c]) st.pop_back();
rig[r][c] = (st.empty() ? -1 : st.back());
st.push_back(c);
if (rig[r][c] != -1 && rig[r][c] != c + 1) v[r].push_back({c + 1, rig[r][c] - 1});
}
sort(v[r].begin(), v[r].end());
v[r].erase(unique(v[r].begin(), v[r].end()), v[r].end());
}
inline int sum (int a, int b) {
if (a == 0) return ok[b];
return ok[b] - ok[a - 1];
}
void add_row (int r) {
for (auto par : v[r]) {
int a = par.first, b = par.second;
cnt[a][b]++;
if (cnt[a][b] == curr && sum(a, b) == 0) sol++;
}
}
llint count_rectangles (vector<vector<int>> A) {
n = A.size(), m = A[0].size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
a[i][j] = A[i][j];
}
}
for (int r = 0; r < n; r++) precompute_row(r);
for (int r1 = 0; r1 < n; r1++) {
memset(cnt, 0, sizeof cnt);
memset(mx, 0, sizeof mx);
curr = 0;
for (int r2 = r1 + 2; r2 < n; r2++) {
for (int c = 0; c < m; c++) {
mx[c] = max(mx[c], a[r2 - 1][c]);
if (mx[c] < a[r1][c] && mx[c] < a[r2][c]) ok[c] = 0; else ok[c] = 1;
if (c > 0) ok[c] += ok[c - 1];
}
curr++;
add_row(r2 - 1);
}
}
return sol;
}
