#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2525;
int n, m, U[N][N], D[N][N], L[N][N], R[N][N];
vector<pair<int, int>> ver[N], hor[N];
vector<pair<int, int>> my_ver[N][N];
vector<pair<int, int>> my_hor[N][N];
vector<pair<int, int>> clear_vec(vector<pair<int, int>> vec, int x, int y) {
vector<pair<int, int>> new_vec;
for (auto& p : vec) {
if (abs(p.first - x) <= 1 || abs(p.second - y) <= 1) {
continue;
}
new_vec.push_back(p);
}
return new_vec;
}
ll count_rectangles(vector<vector<int>> a) {
n = a.size(), m = a[0].size();
// find U
for (int j = 0; j < m; j++) {
vector<int> stk;
for (int i = 0; i < n; i++) {
while (!stk.empty() && a[i][j] > a[stk.back()][j]) {
stk.pop_back();
}
U[i][j] = (stk.empty() ? -1 : stk.back());
stk.push_back(i);
}
}
// find D
for (int j = 0; j < m; j++) {
vector<int> stk;
for (int i = n - 1; i >= 0; i--) {
while (!stk.empty() && a[i][j] > a[stk.back()][j]) {
stk.pop_back();
}
D[i][j] = (stk.empty() ? -1 : stk.back());
stk.push_back(i);
}
}
// find L
for (int i = 0; i < n; i++) {
vector<int> stk;
for (int j = 0; j < m; j++) {
while (!stk.empty() && a[i][j] > a[i][stk.back()]) {
stk.pop_back();
}
L[i][j] = (stk.empty() ? -1 : stk.back());
stk.push_back(j);
}
}
// find R
for (int i = 0; i < n; i++) {
vector<int> stk;
for (int j = m - 1; j >= 0; j--) {
while (!stk.empty() && a[i][j] > a[i][stk.back()]) {
stk.pop_back();
}
R[i][j] = (stk.empty() ? -1 : stk.back());
stk.push_back(j);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (R[i][j] != -1 && R[i][j] != j + 1)
hor[j].emplace_back(R[i][j], i);
if (L[i][j] != -1 && L[i][j] != j - 1)
hor[L[i][j]].emplace_back(j, i);
if (U[i][j] != -1 && U[i][j] != i - 1)
ver[U[i][j]].emplace_back(i, j);
if (D[i][j] != -1 && D[i][j] != i + 1)
ver[i].emplace_back(D[i][j], j);
}
}
for (int j = 0; j < m - 2; j++) {
sort(hor[j].begin(), hor[j].end());
int sz = hor[j].size();
for (int l = 0; l < sz; l++) {
int r = l;
while (r + 1 < sz && hor[j][r + 1].first == hor[j][l].first) r++;
for (int x = l; x <= r; x++) {
int y = x;
while (y + 1 <= r && hor[j][y + 1].second == hor[j][y].second + 1) y++;
for (int z = x; z < y; z++) {
my_hor[hor[j][z].second][j].emplace_back(min(n - 1, hor[j][y].second + 1), hor[j][y].first); // format (i, j)
}
if (hor[j][x].second > 0) {
my_hor[hor[j][x].second - 1][j].emplace_back(min(n - 1, hor[j][y].second + 1), hor[j][y].first); // format (i, j)
}
x = y;
}
l = r;
}
}
for (int i = 0; i < n; i++) {
sort(ver[i].begin(), ver[i].end());
int sz = ver[i].size();
for (int l = 0; l < sz; l++) {
int r = l;
while (r + 1 < sz && ver[i][r + 1].first == ver[i][l].first) r++;
for (int x = l; x <= r; x++) {
int y = x;
while (y + 1 <= r && ver[i][y + 1].second == ver[i][y].second + 1) y++;
for (int z = x; z < y; z++) {
my_ver[i][ver[i][z].second].emplace_back(ver[i][y].first, min(m - 1, ver[i][y].second + 1)); // format (i, j)
}
if (ver[i][x].second > 0) {
my_ver[i][ver[i][x].second - 1].emplace_back(ver[i][y].first, min(m - 1, ver[i][y].second + 1)); // format (i, j)
}
x = y;
}
l = r;
}
}
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// printf("(%d, %d): ", i, j);
// for (auto& p : my_ver[i][j]) {
// printf("[%d, %d] ", p.first, p.second);
// }
// printf("\n");
// }
// }
//
// printf("\n");
// printf("\n");
// printf("\n");
// printf("\n");
// printf("\n");
//
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// printf("(%d, %d): ", i, j);
// for (auto& p : my_hor[i][j]) {
// printf("[%d, %d] ", p.first, p.second);
// }
// printf("\n");
// }
// }
for (int i = 0; i < n - 2; i++) {
for (int j = 0; j < m - 2; j++) {
sort(my_hor[i][j].begin(), my_hor[i][j].end());
my_hor[i][j] = clear_vec(my_hor[i][j], i, j);
my_hor[i][j].erase(unique(my_hor[i][j].begin(), my_hor[i][j].end()), my_hor[i][j].end());
sort(my_ver[i][j].begin(), my_ver[i][j].end());
my_ver[i][j] = clear_vec(my_ver[i][j], i, j);
my_ver[i][j].erase(unique(my_ver[i][j].begin(), my_ver[i][j].end()), my_ver[i][j].end());
}
}
ll ans = 0;
for (int i = 0; i < n - 2; i++) {
for (int j = 0; j < m - 2; j++) {
for (auto& r : my_hor[i][j]) {
for (auto& b : my_ver[i][j]) {
if (b.first <= r.first && b.second >= r.second) {
ans++;
}
}
}
}
}
return ans;
}
