#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> ms(vector<int> &a, bool f) {
int n = a.size();
vector<int> b(n, f ? n : -1), stk;
for (int i = (f ? n - 1 : 0); i != (f ? -1 : n); i += (f ? -1 : 1)) {
while (!stk.empty() && a[stk.back()] < a[i]) {
stk.pop_back();
}
if (!stk.empty()) {
b[i] = stk.back();
}
stk.push_back(i);
}
return b;
}
int lg[2501];
struct sparse_table {
int n, e;
int (*f)(int, int);
vector<vector<int>> st;
sparse_table() {
}
sparse_table(vector<int> &a, int (*_f)(int, int), int _e) : n(a.size()), f(_f), e(_e) {
st = vector(n, vector<int>(lg[n] + 1, e));
for (int i = 0; i < n; i++) {
st[i][0] = a[i];
}
for (int j = 0; j < lg[n]; j++) {
for (int i = 0; i + (2 << j) <= n; i++) {
st[i][j + 1] = f(st[i][j], st[i + (1 << j)][j]);
}
}
}
int query(int l, int r) {
if (l == r) {
return e;
}
int k = lg[r - l];
return f(st[l][k], st[r - (1 << k)][k]);
}
};
int fmin(int x, int y) {
return min(x, y);
}
int fmax(int x, int y) {
return max(x, y);
}
int n, m;
vector<vector<int>> a;
int L[2500][2500];
int R[2500][2500];
int U[2500][2500];
int D[2500][2500];
int DL[2500][2500];
int DR[2500][2500];
int UL[2500][2500];
int UR[2500][2500];
int LD[2500][2500];
int LU[2500][2500];
int RD[2500][2500];
int RU[2500][2500];
int ans = 0;
int check(int x1, int y1, int x2, int y2) {
if (x1 > x2 || y1 > y2 || x1 < 1 || y1 < 1 || x2 >= n - 1 || y2 >= m - 1) {
return 0;
}
assert(R[x1][y1 - 1] == y2 + 1);
if (a[x1][y1 - 1] <= a[x1][y2 + 1]) {
if (R[x1][y1 - 1] != y2 + 1) {
return 0;
}
if (RD[x1][y1 - 1] <= x2) {
return 0;
}
}
if (a[x2][y1 - 1] <= a[x2][y2 + 1]) {
if (R[x2][y1 - 1] != y2 + 1) {
return 0;
}
if (RU[x2][y1 - 1] >= x1) {
return 0;
}
}
if (a[x2][y1 - 1] >= a[x2][y2 + 1]) {
if (L[x2][y2 + 1] != y1 - 1) {
return 0;
}
if (LU[x2][y2 + 1] >= x1) {
return 0;
}
}
if (a[x1 - 1][y1] <= a[x2 + 1][y1]) {
if (D[x1 - 1][y1] != x2 + 1) {
return 0;
}
if (DR[x1 - 1][y1] <= y2) {
return 0;
}
}
if (a[x1 - 1][y1] >= a[x2 + 1][y1]) {
if (U[x2 + 1][y1] != x1 - 1) {
return 0;
}
if (UR[x2 + 1][y1] <= y2) {
return 0;
}
}
if (a[x1 - 1][y2] <= a[x2 + 1][y2]) {
if (D[x1 - 1][y2] != x2 + 1) {
return 0;
}
if (DL[x1 - 1][y2] >= y1) {
return 0;
}
}
if (a[x1 - 1][y2] >= a[x2 + 1][y2]) {
if (U[x2 + 1][y2] != x1 - 1) {
return 0;
}
if (UL[x2 + 1][y2] >= y1) {
return 0;
}
}
return 1;
}
void solve(int eq) {
for (int i = 0; i < n; i++) {
auto l = ms(a[i], 0);
auto r = ms(a[i], 1);
copy(l.begin(), l.end(), L[i]);
copy(r.begin(), r.end(), R[i]);
}
for (int j = 0; j < m; j++) {
vector<int> v(n);
for (int i = 0; i < n; i++) {
v[i] = a[i][j];
}
auto u = ms(v, 0);
auto d = ms(v, 1);
for (int i = 0; i < n; i++) {
U[i][j] = u[i];
D[i][j] = d[i];
}
}
vector T(n, vector<vector<int>>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (U[i][j] != -1) {
T[U[i][j]][j].push_back(i);
}
}
}
for (int j = 1; j < m - 1; j++) {
vector<int> vl(n), vr(n);
for (int i = 0; i < n; i++) {
vl[i] = L[i][j + 1];
vr[i] = R[i][j - 1];
}
sparse_table sl(vl, fmax, -1);
sparse_table sr(vr, fmin, m);
for (int i = 0; i < n; i++) {
if (i + 1 < n - 1 && D[i][j] != n) {
DL[i][j] = sl.query(i + 1, D[i][j]);
DR[i][j] = sr.query(i + 1, D[i][j]);
}
if (i - 1 > 0 && U[i][j] != -1) {
UL[i][j] = sl.query(U[i][j] + 1, i);
UR[i][j] = sr.query(U[i][j] + 1, i);
}
}
}
for (int i = 1; i < n - 1; i++) {
vector<int> vu(m), vd(m);
for (int j = 0; j < m; j++) {
vu[j] = U[i + 1][j];
vd[j] = D[i - 1][j];
}
sparse_table su(vu, fmax, -1);
sparse_table sd(vd, fmin, n);
for (int j = 0; j < m; j++) {
if (j + 1 < m - 1 && R[i][j] != m) {
RU[i][j] = su.query(j + 1, R[i][j]);
RD[i][j] = sd.query(j + 1, R[i][j]);
}
if (j - 1 > 0 && L[i][j] != -1) {
LU[i][j] = su.query(L[i][j] + 1, j);
LD[i][j] = sd.query(L[i][j] + 1, j);
}
}
}
for (int i = 1; i < n - 1; i++) {
for (int j = 1; j < m - 1; j++) {
int y = R[i][j - 1] - 1;
if (y != m - 1 && (eq || a[i][j - 1] != a[i][y + 1])) {
int x = D[i - 1][j] - 1;
if (x != n - 1) {
ans += check(i, j, x, y);
}
for (int k : T[i - 1][j]) {
if (a[i - 1][j] != a[k][j]) {
ans += check(i, j, k - 1, y);
}
}
}
}
}
}
ll count_rectangles(vector<vector<int>> A) {
swap(a, A);
for (int i = 2; i <= 2500; i++) {
lg[i] = lg[i / 2] + 1;
}
n = a.size();
m = a[0].size();
solve(1);
for (int i = 0; i < n; i++) {
reverse(a[i].begin(), a[i].end());
}
solve(0);
return ans;
}
