#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2005;
const pair<int, int> neg = make_pair(-1, -1);
int n, m;
int a[N][N];
pair<int, int> L[N][N];
pair<int, int> R[N][N];
pair<int, int> D[N][N];
pair<int, int> U[N][N];
ll 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];
L[i][j] = neg;
R[i][j] = neg;
U[i][j] = neg;
D[i][j] = neg;
}
}
vector<tuple<int, int, int, int>> good;
for (int i = 0; i < n; i++) {
stack<pair<int, int>> stk;
for (int j = 0; j < m; j++) {
while (!stk.empty() && a[stk.top().first][stk.top().second] < a[i][j]) {
stk.pop();
}
if (!stk.empty()) {
L[i][j] = stk.top();
good.emplace_back(stk.top().first, stk.top().second, i, j);
}
stk.push({i, j});
}
}
for (int i = 0; i < n; i++) {
stack<pair<int, int>> stk;
for (int j = m - 1; j >= 0; j--) {
while (!stk.empty() && a[stk.top().first][stk.top().second] < a[i][j]) {
stk.pop();
}
if (!stk.empty()) {
R[i][j] = stk.top();
good.emplace_back(i, j, stk.top().first, stk.top().second);
}
stk.push({i, j});
}
}
for (int j = 0; j < m; j++) {
stack<pair<int, int>> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[stk.top().first][stk.top().second] < a[i][j]) {
stk.pop();
}
if (!stk.empty()) {
U[i][j] = stk.top();
good.emplace_back(stk.top().first, stk.top().second, i, j);
}
stk.push({i, j});
}
}
for (int j = 0; j < m; j++) {
stack<pair<int, int>> stk;
for (int i = n - 1; i >= 0; i--) {
while (!stk.empty() && a[stk.top().first][stk.top().second] < a[i][j]) {
stk.pop();
}
if (!stk.empty()) {
D[i][j] = stk.top();
good.emplace_back(i, j, stk.top().first, stk.top().second);
}
stk.push({i, j});
}
}
/*cout << "L:\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << L[i][j].first << " " << L[i][j].second << " ";
}
cout << "\n";
cout << "\n";
}*/
//cout << D[1][1].first << " " << D[1][1].second << "\n";
ll ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int cnt_my = 0;
for (int len = 1; len < i; len++) {
for (int x = 1; x < j; x++) {
bool ok = true;
for (int c = 1; c <= x; c++) {
pair<int, int> my = {i, j - c};
pair<int, int> his = {i - len - 1, j - c};
if ((U[my.first][my.second] != neg && U[my.first][my.second].first > his.first) || (D[his.first][his.second] != neg && D[his.first][his.second].first < my.first)) {
ok = false;
}
}
for (int c = 1; c <= len; c++) {
pair<int, int> my = {i - c, j};
pair<int, int> his = {i - c, j - x - 1};
if ((L[my.first][my.second] != neg && L[my.first][my.second].second > his.second) || (R[his.first][his.second] != neg && R[his.first][his.second].second < my.second)) {
ok = false;
}
}
ans += ok;
cnt_my += ok;
/*if (ok) {
cout << i - len + 1 << " " << j - x + 1 << " " << i << " " << j << endl;
}*/
}
}
assert(cnt_my <= 8);
}
}
return ans;
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/
