#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MP make_pair
long long count_rectangles(vector<vector<int>> A) {
const int N = A.size(), M = A[0].size();
vector<pair<int, pair<int, int>>> hor;
vector<pair<int, pair<int, int>>> ver;
for (int i = 0; i < N; i++){
for (int j1 = 0; j1 < M - 2; j1++){
int mx = A[i][j1 + 1];
for (int j2 = j1 + 2; j2 < M; j2++){
if (mx < min(A[i][j1], A[i][j2])){
hor.emplace_back(i, MP(j1, j2));
}
mx = max(mx, A[i][j2]);
}
}
}
for (int j = 0; j < M; j++) {
for (int i1 = 0; i1 < N - 2; i1++) {
int mx = A[i1 + 1][j];
for (int i2 = i1 + 2; i2 < N; i2++) {
if (mx < min(A[i1][j], A[i2][j])){
ver.emplace_back(j, MP(i1, i2));
}
mx = max(mx, A[i2][j]);
}
}
}
assert((int)max(hor.size(), ver.size()) <= 4 * N * M);
map<vector<int>, int> mp;
for (auto x : hor){
for (auto y : ver){
int i = x.first, j1 = x.second.first, j2 = x.second.second;
int j = y.first, i1 = y.second.first, i2 = y.second.second;
if (i1 < i && i < i2 && j1 < j && j < j2){
mp[{i1, j1, i2, j2}]++;
}
}
}
ll ans = 0;
for (auto now : mp){
vector<int> v = now.first;
if ((v[2] - v[0] - 1) * (v[3] - v[1] - 1) == now.second){
ans++;
}
}
return ans;
}
