#include <bits/stdc++.h>
using namespace std;
const int N = 2525, A = 7e6;
int m, n, a[N][N];
int l[N][N], r[N][N], u[N][N], d[N][N];
int treeRow[N][N], treeCol[N][N];
vector<pair<int, int>> id[A + 5];
void addTree(int tree[], int x)
{
for (int i = x; i < N; i += i & -i)
tree[i]++;
}
int getTree(int tree[], int x)
{
int res = 0;
for (int i = x; i; i -= i & -i)
res += tree[i];
return res;
}
void add(int x, int y)
{
addTree(treeRow[x], y);
addTree(treeCol[y], x);
l[x][r[x][y]] = l[x][y];
r[x][l[x][y]] = r[x][y];
u[d[x][y]][y] = u[x][y];
d[u[x][y]][y] = d[x][y];
}
int isEmpty(int tree[], int from, int to)
{
return getTree(tree, to) == getTree(tree, from - 1);
}
int isFull(int tree[], int from, int to)
{
return getTree(tree, to) - getTree(tree, from - 1) == to - from + 1;
}
int isRect(int x, int y)
{
int curL = l[x][y] + 1, curR = r[x][y] - 1, curU = u[x][y] + 1, curD = d[x][y] - 1;
if (curL < 2 || curU < 2 || curR > n - 1 || curL > m - 1)
return 0;
if (a[x][y] >= min({a[x][curL - 1], a[x][curR + 1], a[curU - 1][y], a[curD + 1][y]}))
return 0;
if (!isFull(treeRow[curU], curL, curR) || !isFull(treeRow[curD], curL, curR))
return 0;
if (!isFull(treeCol[curL], curU, curD) || !isFull(treeCol[curR], curU, curD))
return 0;
return 1;
}
long long count_rectangles(vector<vector<int>> _a)
{
m = _a.size();
n = _a[0].size();
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
{
id[_a[i - 1][j - 1]].push_back({i, j});
a[i][j] = _a[i - 1][j - 1];
u[i][j] = i - 1;
d[i][j] = i + 1;
l[i][j] = j - 1;
r[i][j] = j + 1;
}
long long ans = 0;
for (int v = 0; v <= A; v++)
if (!id[v].empty())
{
for (auto u : id[v])
add(u.first, u.second);
for (auto u : id[v])
ans += isRect(u.first, u.second);
}
return ans;
}
