#include "rect.h"
#include<bits/stdc++.h>
using namespace std;
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
// #define int long long
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
void mnn(int &a, int b) {
if(a > b) a = b;
}
void mxx(int &a, int b) {
if(a < b) a = b;
}
const int mxn = 2510;
namespace sub6 {
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
int par[mxn * mxn], cnt[mxn * mxn], n, m;
pair<pair<int, int>, pair<int, int>> dp[mxn * mxn];
bool is[mxn][mxn];
int toInt(pair<int, int> a) {
return (a.ff - 1) * n + a.ss;
}
int get(int x) {
if(par[x] == x) return x;
return par[x] = get(par[x]);
}
void unite(int x, int y) {
x = get(x), y = get(y);
if(x == y) return;
if(cnt[x] < cnt[y]) swap(x, y);
par[y] = x;
cnt[x] += cnt[y];
mxx(dp[x].ss.ff, dp[y].ss.ff);
mxx(dp[x].ss.ss, dp[y].ss.ss);
mnn(dp[x].ff.ff, dp[y].ff.ff);
mnn(dp[x].ff.ss, dp[y].ff.ss);
}
long long count_rectangles(vector<vector<int>> A) {
n = A.size(), m = A[0].size();
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(A[i][j] == 0) {
dp[i * m + j] = {{i, j}, {i, j}};
par[i * m + j] = i * m + j;
cnt[i * m + j] = 1;
}
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(A[i][j]) continue;
for(int k = 0; k < 4; k++) {
int ii = i + dx[k], jj = j + dy[k];
if(ii >= 0 && ii < n && jj >= 0 && jj < m && A[ii][jj] == 0) {
unite(i * m + j, ii * m + jj);
}
}
}
}
long long ret = 0;
set<int> s;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(A[i][j] == 1) continue;
int id = get(i * m + j);
if(s.find(id) != s.end()) continue;
s.in(id);
if((dp[id].ss.ff - dp[id].ff.ff + 1) * (dp[id].ss.ss - dp[id].ff.ss + 1) == cnt[id] &&
dp[id].ff.ff > 0 && dp[id].ff.ss > 0 && dp[id].ss.ff < n - 1 && dp[id].ss.ss < m - 1) ret++;
}
}
return ret;
}
}
int n, m, a[mxn][mxn], mx[mxn], fn[mxn];
vector<pair<int, int>> g[mxn];
int get(int i) {
int ret = 0;
for(; i > 0; i -= (i & -i)) {
ret += fn[i];
}
return ret;
}
void add(int i, int x) {
for(; i <= m; i += (i & -i)) {
fn[i] += x;
}
}
long long count_rectangles(vector<vector<int>> A) {
n = A.size(), m = A[0].size();
int MX = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
a[i][j] = A[i - 1][j - 1];
if(MX < a[i][j]) MX = a[i][j];
}
}
if(MX <= 1) return sub6::count_rectangles(A);
for(int i = 1; i <= n; i++) {
stack<pair<int, int>> s;
for(int j = 1; j <= m; j++) {
while(s.size() && s.top().ff < a[i][j]) {
if(s.top().ss + 1 < j) g[i].eb(s.top().ss, j);
s.pop();
}
if(s.size()) {
if(s.top().ss + 1 < j) g[i].eb(s.top().ss, j);
if(s.top().ff == a[i][j]) {
s.pop();
}
}
s.push({a[i][j], j});
}
sort(all(g[i]));
}
long long ans = 0;
for(int l = 2; l < n; l++) {
for(int j = 1; j <= m; j++) {
mx[j] = -1;
fn[j] = 0;
}
vector<pair<int, int>> v;
for(int r = l; r <= n; r++) {
for(int j = 1; j <= m; j++) {
if(mx[j] >= a[r][j]) add(j, 1);
}
if(r == l) {
v = g[r];
} else {
for(auto it : v) {
ans += (get(it.ss - 1) - get(it.ff) == 0);
}
vector<pair<int, int>> tmp;
int id1 = 0, id2 = 0;
while(id1 < v.size() && id2 < g[r].size()) {
if(v[id1] == g[r][id2]) {
tmp.pb(v[id1]);
id1++;
id2++;
} else if(v[id1] < g[r][id2]) {
id1++;
} else {
id2++;
}
}
swap(tmp, v);
}
for(int j = 1; j <= m; j++) {
if(mx[j] >= a[r][j]) add(j, -1);
else {
if(a[r][j] >= a[l - 1][j]) add(j, 1);
mx[j] = a[r][j];
}
}
}
}
return ans;
}
