#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
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> st;
void solve(bool eqL, bool eqC) {
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];
if (l2 > n || c2 > m || l2 - l1 <= 1 || c2 - c1 <= 1)
continue;
if (mat[l1 + 1][c1] == mat[l1 + 1][c2] && eqL)
continue;
if (mat[l1][c1 + 1] == mat[l2][c1 + 1] && eqC)
continue;
bool ok = true;
for (int l = l1 + 1; l <= l2 - 1; l++)
ok |= (rightGE[l][c1] == c2 || (leftGE[l][c2] == c1));
for (int c = c1 + 1; c <= c2 - 1; c++)
ok |= (downGE[l1][c] == l2 || (upGE[l2][c] == l1));
// if (ok)
// printf("%d %d %d %d\n", l1, c1, l2, c2);
ans += ok;
}
}
}
void rotVert() {
for (int l = 1; l <= n; l++) {
for (int c = 1; c <= m / 2; c++) {
swap(mat[l][c], mat[l][c + 1 - m]);
swap(upG[l][c], upG[l][m + 1 - c]);
swap(upGE[l][c], upGE[l][m + 1 - c]);
swap(downGE[l][c], downGE[l][m + 1 - c]);
swap(downG[l][c], downG[l][m + 1 - c]);
}
}
for (int l = 1; l <= n; l++) {
for (int c = 1; c <= m; c++) {
swap(leftG[l][c], rightG[l][m + 1 - c]);
swap(leftGE[l][c], rightGE[l][m + 1 - c]);
swap(rightG[l][c], leftG[l][m + 1 - c]);
swap(rightGE[l][c], leftGE[l][m + 1 - c]);
}
}
}
void rotHoriz() {
for (int l = 1; l <= n / 2; l++) {
for (int c = 1; c <= m; c++) {
swap(mat[l][c], mat[n + 1 - l][c]);
swap(leftG[l][c], leftG[n + 1 - l][c]);
swap(leftGE[l][c], leftGE[n + 1 - l][c]);
swap(rightG[l][c], rightG[n + 1 - l][c]);
swap(rightGE[l][c], rightGE[n + 1 - l][c]);
}
}
for (int l = 1; l <= n; l++) {
for (int c = 1; c <= m; c++) {
swap(upG[l][c], upG[n + 1 - l][c]);
swap(upGE[l][c], downGE[n + 1 - l][c]);
swap(downG[l][c], upG[n + 1 - l][c]);
swap(downGE[l][c], upGE[n + 1 - l][c]);
}
}
}
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];
}
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);
}
}
/*
for (int l = 1; l <= n; l++) {
for (int c = 1; c <= m; c++)
printf("%d ", leftG[l][c]);
printf("\n");
}
*/
/*
for (int l = 1; l <= n; l++) {
for (int c = 1; c <= m; c++)
printf("%d ", downGE[l][c]);
printf("\n");
}
*/
for (int a = 0; a < 2; a++) {
for (int b = 0; b < 2; b++) {
solve(a, b);
rotVert();
}
rotHoriz();
}
return ans;
}
