#include <bits/stdc++.h>
#include "rect.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const int N = 2507;
int b[N][N][4], h[N][N], res[N*N];
struct tri {
int x, y, z, ix;
};
vector <tri> qu[N], qu2[N];
ll count_rectangles(vector <vector <int> > a) {
int n = a.size(), m = a[0].size();
for (int i = 0; i < n; i++) {
stack <int> st;
for (int j = 0; j < m; j++) {
while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
if (st.empty()) b[i][j][0] = -1;
else b[i][j][0] = st.top();
st.push(j);
}
while (!st.empty()) st.pop();
for (int j = m-1; j >= 0; j--) {
while (!st.empty() && a[i][st.top()] <= a[i][j]) st.pop();
if (st.empty()) b[i][j][1] = -1;
else b[i][j][1] = st.top();
st.push(j);
}
}
for (int j = 0; j < m; j++) {
stack <int> st;
for (int i = 0; i < n; i++) {
while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
if (st.empty()) b[i][j][2] = -1;
else b[i][j][2] = st.top();
st.push(i);
}
while (!st.empty()) st.pop();
for (int i = n-1; i >= 0; i--) {
while (!st.empty() && a[st.top()][j] <= a[i][j]) st.pop();
if (st.empty()) b[i][j][3] = -1;
else b[i][j][3] = st.top();
st.push(i);
}
}
auto good = [&](int x, int y, int o) {return b[x][y][2*o] != -1 && b[x][y][2*o+1] != -1;};
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < m-1; j++) {
if (good(i, j, 0) && good(i, j, 1)) {
qu[b[i][j][3]-1].pb({b[i][j][0], b[i][j][1], b[i][j][2], i*m+j});
qu2[b[i][j][1]-1].pb({b[i][j][2], b[i][j][3], b[i][j][0], i*m+j});
}
}
}
int cnt = 0;
for (int i = 1; i < n-1; i++) {
for (int j = 1; j < m-1; j++) if (good(i-1, j, 0) && h[b[i-1][j][0]][b[i-1][j][1]] >= 0) h[b[i-1][j][0]][b[i-1][j][1]] *= -1;
for (int j = 1; j < m-1; j++) if (good(i, j, 0) && h[b[i][j][0]][b[i][j][1]] <= 0) h[b[i][j][0]][b[i][j][1]] = -h[b[i][j][0]][b[i][j][1]]+1;
for (int j = 1; j < m-1; j++) if (good(i-1, j, 0) && h[b[i-1][j][0]][b[i-1][j][1]] < 0) h[b[i-1][j][0]][b[i-1][j][1]] = 0;
for (auto x : qu[i]) {
if (i - x.z <= h[x.x][x.y]) res[x.ix]++;
}
}
memset(h, 0, sizeof h);
for (int j = 1; j < m-1; j++) {
for (int i = 1; i < n-1; i++) if (good(i, j-1, 1) && h[b[i][j-1][2]][b[i][j-1][3]] >= 0) h[b[i][j-1][2]][b[i][j-1][3]] *= -1;
for (int i = 1; i < n-1; i++) if (good(i, j, 1) && h[b[i][j][2]][b[i][j][3]] <= 0) h[b[i][j][2]][b[i][j][3]] = -h[b[i][j][2]][b[i][j][3]]+1;
for (int i = 1; i < n-1; i++) if (good(i, j-1, 1)) if (h[b[i][j-1][2]][b[i][j-1][3]] < 0) h[b[i][j-1][2]][b[i][j-1][3]] = 0;
for (auto x : qu2[j]) {
if (j - x.z <= h[x.x][x.y]) res[x.ix]++;
}
}
map <ll, int> ma;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (res[i*m+j] == 2) {
ll en = 0;
for (int k = 0; k < 4; k++) en = (en << 16) + b[i][j][k];
cnt += !ma[en];
ma[en] = 1;
}
}
}
return cnt;
}
