#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
struct rect {
int l1, c1, l2, c2;
bool operator < (const rect &x) const {
if (l1 == x.l1) {
if (c1 == x.c1) {
if (l2 == x.l2)
return c2 < x.c2;
return l2 < x.l2;
}
return c1 < x.c1;
}
return l1 < x.l1;
}
bool operator == (const rect &x) const {
if (x < *this)
return false;
if (*this < x)
return false;
return true;
}
};
const int MAX_N = 2500;
const int INF = 1e9;
int n, m;
long long ans = 0;
int mat[MAX_N + 2][MAX_N + 2];
int leftG[MAX_N + 2][MAX_N + 2], leftGE[MAX_N + 2][MAX_N + 2];
int rightG[MAX_N + 2][MAX_N + 2], rightGE[MAX_N + 2][MAX_N + 2];
int upG[MAX_N + 2][MAX_N + 2], upGE[MAX_N + 2][MAX_N + 2];
int downG[MAX_N + 2][MAX_N + 2], downGE[MAX_N + 2][MAX_N + 2];
vector<int> l2s[MAX_N + 2][MAX_N + 2];
vector<int> c2s[MAX_N + 2][MAX_N + 2];
vector<rect> cand;
vector<int> st;
void init() {
for (int l = 1; l <= n; l++) {
mat[l][0] = INF;
st.clear();
st.push_back(0);
for (int c = 1; c <= m; c++) {
while (mat[l][c] > mat[l][st.back()])
st.pop_back();
leftGE[l][c] = st.back();
st.push_back(c);
}
st.clear();
st.push_back(0);
for (int c = 1; c <= m; c++) {
while (mat[l][c] >= mat[l][st.back()])
st.pop_back();
leftG[l][c] = st.back();
st.push_back(c);
}
mat[l][m + 1] = INF;
st.clear();
st.push_back(m + 1);
for (int c = m; c >= 1; c--) {
while (mat[l][c] > mat[l][st.back()])
st.pop_back();
rightGE[l][c] = st.back();
st.push_back(c);
}
st.clear();
st.push_back(m + 1);
for (int c = m; c >= 1; c--) {
while (mat[l][c] >= mat[l][st.back()])
st.pop_back();
rightG[l][c] = st.back();
st.push_back(c);
}
}
for (int c = 1; c <= m; c++) {
mat[0][c] = INF;
st.clear();
st.push_back(0);
for (int l = 1; l <= n; l++) {
while (mat[l][c] > mat[st.back()][c])
st.pop_back();
upGE[l][c] = st.back();
st.push_back(l);
}
st.clear();
st.push_back(0);
for (int l = 1; l <= n; l++) {
while (mat[l][c] >= mat[st.back()][c])
st.pop_back();
upG[l][c] = st.back();
st.push_back(l);
}
mat[n + 1][c] = INF;
st.clear();
st.push_back(n + 1);
for (int l = n; l >= 1; l--) {
while (mat[l][c] > mat[st.back()][c])
st.pop_back();
downGE[l][c] = st.back();
st.push_back(l);
}
st.clear();
st.push_back(n + 1);
for (int l = n; l >= 1; l--) {
while (mat[l][c] >= mat[st.back()][c])
st.pop_back();
downG[l][c] = st.back();
st.push_back(l);
}
}
}
void solve1() {
init();
for (int l1 = 1; l1 <= n; l1++) {
for (int c1 = 1; c1 <= m; c1++) {
int c2 = rightGE[l1 + 1][c1], l2 = downGE[l1][c1 + 1];
for (int l2 = l1; l2 <= n; l2++) {
for (int c2 = c1; c2 <= m; c2++) {
if (l2 > n || c2 > m || l2 - l1 <= 1 || c2 - c1 <= 1)
continue;
bool ok = true;
for (int l = l1 + 1; l <= l2 - 1 && ok; l++)
ok &= (rightGE[l][c1] == c2 || (leftGE[l][c2] == c1));
for (int c = c1 + 1; c <= c2 - 1 && ok; c++)
ok &= (downGE[l1][c] == l2 || (upGE[l2][c] == l1));
/*
if (ok)
printf("%d %d %d %d\n\n", l1, c1, l2, c2);
*/
ans += ok;
}
}
}
}
}
void solve2() {
init();
for (auto x: cand) {
int l1 = x.l1, l2 = x.l2, c1 = x.c1, c2 = x.c2;
if (l1 < 1 || c1 < 1 || l2 > n || c2 > m || l2 - l1 <= 1 || c2 - c1 <= 1)
continue;
//printf("%d %d %d %d\n\n", l1, c1, l2, c2);
bool ok = true;
for (int l = l1 + 1; l <= l2 - 1 && ok; l++)
ok &= (rightGE[l][c1] == c2 || (leftGE[l][c2] == c1));
for (int c = c1 + 1; c <= c2 - 1 && ok; c++)
ok &= (downGE[l1][c] == l2 || (upGE[l2][c] == l1));
/*
if (ok)
printf("%d %d %d %d\n\n", l1, c1, l2, c2);
*/
ans += ok;
}
}
long long count_rectangles(vector<vector<int>> a) {
n = a.size(), m = a[0].size();
for (int l = 1; l <= n; l++) {
for (int c = 1; c <= m; c++)
mat[l][c] = a[l - 1][c - 1];
}
init();
for (int l = 1; l <= n; l++) {
for (int c = 1; c <= m; c++) {
l2s[upGE[l][c]][c - 1].push_back(l);
c2s[l - 1][leftGE[l][c]].push_back(c);
}
}
for (int l = 1; l <= n; l++) {
for (int c = 1; c <= m; c++) {
l2s[l][c].push_back(downGE[l][c + 1]);
c2s[l][c].push_back(rightGE[l + 1][c]);
for (int l2: l2s[l][c]) {
for (int c2: c2s[l][c])
cand.push_back({l, c, l2, c2});
}
}
}
sort(cand.begin(), cand.end());
cand.resize(unique(cand.begin(), cand.end()) - cand.begin());
//solve1();
solve2();
return ans;
}
