#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<12;
int drz[2 * N];
int tab[N][N];
vector<int> intr[N][N];
vector<pair<int, int>> que[N][N];
bool czy[N];
long long answer = 0;
void Add(int v, int x)
{
v += N;
while(v > 0)
{drz[v] += x; v /= 2;}
}
int Query(int a, int b)
{
a += N - 1; b += N + 1;
int ans = 0;
while(a / 2 != b / 2)
{
if(a % 2 == 0) ans += drz[a + 1];
if(b % 2 == 1) ans += drz[b - 1];
a /= 2; b /= 2;
}
return ans;
}
void CntR(int n, int m)
{
for(int i = 1; i <= n; ++i)
{
vector<pair<int, int>> kol;
for(int j = m; j >= 1; --j)
{
while((int)kol.size() > 0 && kol.back().st <= tab[i][j])
kol.pop_back();
int xd = tab[i][j];
//cerr << "R: " << i << " " << j << "\n";
for(int k = kol.size() - 1; k >= 0 && tab[i][j - 1] > xd; --k)
{
intr[i][j].pb(kol[k].nd - 1);
//cerr << kol[k].nd - 1 << " ";
xd = max(xd, kol[k].st);
}
//cout << "\n";
kol.pb(make_pair(tab[i][j], j));
}
}
for(int j = 1; j <= m; ++j)
{
vector<pair<int, int>> akt;
for(int i = j; i <= m; ++i)
akt.pb(make_pair(i, 1));
for(int i = 1; i <= n; ++i)
{
vector<pair<int, int>> nxt;
int k = 0;
//cerr << "DP: " << i << " " << j << "\n";
for(int l = 0; l < (int)intr[i][j].size(); ++l)
{
while(k < (int)akt.size() && akt[k].st < intr[i][j][l])
++k;
if(k < (int)akt.size() && akt[k].st == intr[i][j][l])
{
nxt.pb(akt[k]);
++k;
}else
nxt.pb(make_pair(intr[i][j][l], i));
que[i][intr[i][j][l]].pb(make_pair(j, i - nxt.back().nd + 1));
//cerr << nxt.back().st << " " << nxt.back().nd << "\n";
}
akt = nxt;
intr[i][j].clear();
}
}
}
void CntL(int n, int m)
{
for(int j = 1; j <= m; ++j)
{
vector<pair<int, int>> kol;
for(int i = 1; i <= n; ++i)
{
while((int)kol.size() > 0 && kol.back().st <= tab[i][j])
kol.pop_back();
int xd = tab[i][j];
//cerr << "U: " << i << " " << j << "\n";
for(int k = kol.size() - 1; k >= 0 && tab[i + 1][j] > xd; --k)
{
intr[i][j].pb(kol[k].nd + 1);
//cerr << kol[k].nd + 1 << "\n";
xd = max(xd, kol[k].st);
}
sort(intr[i][j].begin(), intr[i][j].end());
kol.pb(make_pair(tab[i][j], i));
}
}
for(int i = 1; i <= n; ++i)
{
vector<pair<int, int>> akt;
for(int j = i; j <= n; ++j)
akt.pb(make_pair(j, 1));
for(int j = 1; j <= m; ++j)
{
vector<pair<int, int>> nxt;
int k = 0;
//cerr << "DP: " << i << " " << j << "\n";
for(int l = 0; l < (int)intr[i][j].size(); ++l)
{
while(k < (int)akt.size() && akt[k].st < intr[i][j][l])
++k;
if(k < (int)akt.size() && akt[k].st == intr[i][j][l])
{
nxt.pb(make_pair(akt[k].nd, akt[k].st));
++k;
}else
nxt.pb(make_pair(j, intr[i][j][l]));
//cerr << nxt.back().nd << " " << nxt.back().st << "\n";
}
akt = nxt;
sort(akt.begin(), akt.end());
int lim = akt.size();
k = -1;
//cout << "QUE: " << i << " " << j << "\n";
for(int l = 0; l < (int)que[i][j].size(); ++l)
{
while(k < lim - 1 && akt[k + 1].st <= que[i][j][l].st)
{
++k;
Add(i - akt[k].nd + 1, 1);
}
answer += (ll)Query(0, que[i][j][l].nd);
//for(int r = 0; r < lim; ++r)
//if(akt[r].st <= que[i][j][l].st && i - akt[r].nd + 1 <= que[i][j][l].nd)
//++answer;
}
for(k = k; k >= 0; --k)
Add(i - akt[k].nd + 1, -1);
for(int l = 0; l < (int)akt.size(); ++l)
swap(akt[l].st, akt[l].nd);
sort(akt.begin(), akt.end());
intr[i][j].clear();
}
}
}
long long count_rectangles(vector<vector<int>> xd)
{
int n = xd.size(), m = xd[0].size();
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= m; ++j)
tab[i][j] = xd[i - 1][j - 1];
CntR(n, m);
CntL(n, m);
return answer;
}
