#include <bits/stdc++.h>
#include <math.h>
#include <chrono>
using namespace std;
#pragma GCC optimize("-O3")
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10) //cin.tie(0); cout.tie(0);
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define FWD(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define all(c) (c).begin(), (c).end()
#define what(x) cerr << #x << " is " << x << endl;
const int MAXN = 2502; //UWAGA
vector<int> dol[MAXN][MAXN];
vector<pair<short, short>> R[MAXN][MAXN];
vector<pair<short, short>> D[MAXN][MAXN];
int n, m;
int tab[MAXN][MAXN];
long long ans = 0;
void wypelnij2prawo()
{
rep(j, m)
{
vector<pii> X(3e3, {-1, -1});
for (int i = n - 1; i >= 0; i--)
for (int a : dol[i][j])
{
X[a] = (X[a].st == i + 1) ? mp(i, X[a].nd + 1) : mp(i, 1);
R[i][j].pb({a, X[a].nd}); //glebokosc i ile
}
}
}
void wypelnij2dol()
{
rep(i, n)
{
vector<pii> X(3e3, {-1, -1});
for (int j = m - 1; j >= 0; j--)
{
for (int a : dol[i][j])
{
X[a] = (X[a].st == j + 1) ? mp(j, X[a].nd + 1) : mp(j, 1);
D[i][j].pb({a, X[a].nd}); //glebokosc i ile
}
dol[i][j].resize(0);
dol[i][j].shrink_to_fit();
}
}
}
vector<vector<int>> wypelnij1(vector<int> &Q)
{
vector<vector<int>> P(Q.size());
stack<pii> S;
rep(i, Q.size())
{
while (!S.empty() && S.top().st < Q[i])
S.pop();
if (!S.empty() && i - S.top().nd - 1 > 0)
P[S.top().nd].pb(i - S.top().nd - 1);
S.push(mp(Q[i], i));
}
while (!S.empty())
S.pop();
for (int i = Q.size() - 1; i >= 0; i--)
{
while (!S.empty() && S.top().st < Q[i])
S.pop();
if (!S.empty() && S.top().nd - i - 1 > 0 && S.top().st != Q[i])
P[i].pb(S.top().nd - i - 1);
S.push(mp(Q[i], i));
}
return P;
}
const int rozmiar = (1 << 12);
int ile[3 * rozmiar];
vector<int> zap;
void dodaj(int x)
{
x += rozmiar;
while (x > 0)
{
if (!ile[x])
zap.pb(x);
ile[x]++;
x /= 2;
}
}
int get(int x)
{
int p = rozmiar;
int q = rozmiar + x;
int wynik = 0;
while (p <= q)
{
if (q % 2 == 0)
{
wynik += ile[q];
q--;
}
p /= 2;
q /= 2;
}
//what(wynik);
return wynik;
}
void clear()
{
for (int a : zap)
ile[a] = 0;
zap.clear();
}
void solve(int i, int j)
{
//s cerr << i << " " << j << endl;
if (R[i + 1][j].size() == 0 || D[i][j + 1].size() == 0)
return;
for (auto &B : D[i][j + 1])
swap(B.st, B.nd);
sort(all(R[i + 1][j]), greater<pair<short, short>>());
sort(all(D[i][j + 1]), greater<pair<short, short>>());
/*
cerr << "obecne tutaj::" << endl;
for (auto A : D[i][j + 1])
cerr << A.st << " " << A.nd << endl;
cerr << endl;
for (auto A : R[i + 1][j])
cerr << A.st << " " << A.nd << endl;
cerr << "koniec" << endl;
*/
int k = 0;
int l = 0;
while (l != R[i + 1][j].size() || k != D[i][j + 1].size())
{
if (l == R[i + 1][j].size())
{
dodaj(D[i][j + 1][k].nd);
k++;
continue;
}
if (k == D[i][j + 1].size())
{
ans += get(R[i + 1][j][l].nd);
l++;
continue;
}
if (R[i + 1][j][l].st <= D[i][j + 1][k].st)
{
dodaj(D[i][j + 1][k].nd);
k++;
continue;
}
else
{
ans += get(R[i + 1][j][l].nd);
l++;
continue;
}
}
clear();
}
long long count_rectangles(vector<vector<int32_t>> A)
{
n = A.size();
m = A[0].size();
rep(i, n) rep(j, m) tab[i][j] = A[i][j];
rep(i, n)
{
auto X = wypelnij1(A[i]);
rep(j, m)
dol[i][j] = X[j];
}
wypelnij2prawo();
rep(j, m)
{
vector<int> Y;
rep(i, n)
Y.pb(tab[i][j]);
auto X = wypelnij1(Y);
rep(i, n)
dol[i][j] = X[i];
}
wypelnij2dol();
/*
cerr << "DOL" << endl;
rep(i, n)
{
rep(j, m)
{
cerr << i << " " << j << ":: ";
for (auto a : D[i][j])
cerr << a.st << " " << a.nd << ", ";
cerr << endl;
// cout << a << " /// ";
}
cerr << endl;
}
cerr << "PRAWO" << endl;
rep(i, n)
{
rep(j, m)
{
cerr << i << " " << j << ":: ";
for (auto a : R[i][j])
cerr << a.st << " " << a.nd << ", ";
// cout << a << " /// ";
cerr << endl;
}
cerr << endl;
}
*/
rep(i, n - 1) rep(j, m - 1) solve(i, j);
return ans;
}
