#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <short, short> pii;
const int MAXN = 2.5e3 + 5;
class Fenwick {
int n;
int f[MAXN];
public:
Fenwick(int _n) {
n = _n;
for (int i = 0; i <= n; i++)
f[i] = 0;
}
Fenwick(){}
void update(int x, int val) {
for (x++; x <= n; x += x & -x)
f[x] += val;
}
int get(int x) {
int res = 0;
for (x++; x; x -= x & -x)
res += f[x];
return res;
}
int query(int l, int r) {
return get(r) - get(l - 1);
}
};
short foo[MAXN];
vector <short> rows[MAXN][MAXN], cols[MAXN][MAXN];
vector <pii> in[MAXN][MAXN], out[MAXN][MAXN];
void find_pairs(const vector <int> &arr, vector <short> ref[MAXN][MAXN], int idx) {
int n = arr.size(), sz = 0;
for (int i = 0; i < n; i++) {
while (sz && arr[foo[sz - 1]] < arr[i])
sz--;
if (sz && foo[sz - 1] < i - 1)
ref[foo[sz - 1]][i].push_back(idx);
foo[sz++] = i;
}
sz = 0;
for (int i = n - 1; i >= 0; i--) {
while (sz && arr[foo[sz - 1]] < arr[i])
sz--;
if (sz && arr[foo[sz - 1]] > arr[i] && foo[sz - 1] > i + 1)
ref[i][foo[sz - 1]].push_back(idx);
foo[sz++] = i;
}
}
vector <pii> get_blocks(const vector <short> &v, int bound) {
vector <pii> res;
int sz = v.size(), lst = 0;
for (int i = 0; i < sz; i++)
if (i == sz - 1 || v[i + 1] > v[i] + 1) {
res.push_back({max(v[lst] - 1, 0), min(v[i] + 1, bound - 1)});
lst = i + 1;
}
return res;
}
ll count_rectangles(vector <vector <int>> a) {
int N = a.size();
int M = a[0].size();
for (int i = 0; i < N; i++)
find_pairs(a[i], rows, i);
for (int j = 0; j < M; j++) {
vector <int> curr;
for (int i = 0; i < N; i++)
curr.push_back(a[i][j]);
find_pairs(curr, cols, j);
}
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++) {
vector <pii> tmp = get_blocks(cols[i][j], M);
for (auto it : tmp)
for (int k = it.first; k <= it.second; k++) {
in[k][it.first].push_back({i, j});
out[k][it.second].push_back({i, j});
}
}
ll sol = 0;
vector <Fenwick> loga(N);
for (int i = 0; i < N; i++)
loga[i] = Fenwick(N);
for (int i = 0; i < M; i++)
for (int j = 0; j < M; j++) {
for (auto it : in[i][j])
loga[it.first].update(it.second, 1);
vector <pii> tmp = get_blocks(rows[i][j], N);
for (auto it : tmp)
for (int k = it.first; k <= it.second; k++)
sol += loga[k].query(it.first, it.second);
for (auto it : out[i][j])
loga[it.first].update(it.second, -1);
}
return sol;
}
