#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
long long count_rectangles(vector<vector<int> > a) {
int n = a.size();
int m = a[0].size();
vector<vector<int>> j2(n, vector<int>(m, -1));
vector<vector<int>> j1(n, vector<int>(m, -1));
vector<vector<int>> i2(n, vector<int>(m, -1));
vector<vector<int>> i1(n, vector<int>(m, -1));
for (int i = 0; i < n; i++)
{
vector<int>A;
for (int j = 0; j < m; j++)
{
while (A.size() > 0 && a[i][A.back()] < a[i][j])
A.pop_back();
if (!A.empty())
if (A.back() + 1 <= j - 1)
j1[i][j] = A.back();
A.push_back(j);
}
A.clear();
for (int j = m - 1; j >= 0; j--)
{
while (A.size() > 0 && a[i][A.back()] < a[i][j])
A.pop_back();
if (!A.empty())
if (j + 1 <= A.back() - 1)
j2[i][j] = A.back();
A.push_back(j);
}
}
for (int j = 0; j < m; j++)
{
vector<int>A;
for (int i = 0; i < n; i++)
{
while (A.size() > 0 && a[A.back()][j] < a[i][j])
A.pop_back();
if (!A.empty())
{
if (A.back() + 1 <= i - 1)
i1[i][j] = A.back();
else
i1[i][j] = -1;
}
else
i1[i][j] = -1;
A.push_back(i);
}
A.clear();
for (int i = n - 1; i >= 0; i--)
{
while (A.size() > 0 && a[A.back()][j] < a[i][j])
A.pop_back();
if (!A.empty())
{
if (i + 1 <= A.back() - 1)
i2[i][j] = A.back();
else
i2[i][j] = -1;
}
else
i2[i][j] = -1;
A.push_back(i);
}
}
map<pair<int, int>, int>dpi[n];
map<pair<int, int>, int>dpj[m];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
for (int j_ : {j1[i][j], j2[i][j]})
{
if (j_ != -1)
{
int j1 = j;
int j2 = j_;
if (j1 > j2)
swap(j1, j2);
if (i == 0 || dpi[i - 1].count({j1, j2}) == 0)
dpi[i][ {j1, j2}] = i;
else
dpi[i][ {j1, j2}] = dpi[i - 1][ {j1, j2}];
}
}
}
}
for (int j = 0; j < m; j++)
{
for (int i = 0; i < n; i++)
{
for (int i_ : {i1[i][j], i2[i][j]})
{
if (i_ != -1)
{
int i1 = i;
int i2 = i_;
if (i1 > i2)
swap(i1, i2);
if (j == 0 || dpj[j - 1].count({i1, i2}) == 0)
dpj[j][ {i1, i2}] = j;
else
dpj[j][ {i1, i2}] = dpj[j - 1][ {i1, i2}];
}
}
}
}
long long ans = 0;
set<tuple<int, int, int, int>>S;
auto check = [&](int x1, int x2, int y1, int y2)->void
{
if (x1 == -1 || x2 == -1 || y1 == -1 || y2 == -1)
return;
if (S.count({x1, x2, y1, y2}))
return;
S.insert({x1, x2, y1, y2});
for (int i : {x1 + 1, x2 - 1})
{
if (j2[i][y1] != y2 && j1[i][y2] != y1)
return;
}
for (int j : {y1 + 1, y2 - 1})
{
if (i2[x1][j] != x2 && i1[x2][j] != x1)
return;
}
if (dpi[x2 - 1][{y1, y2}] <= x1 + 1)
if (dpj[y2 - 1][{x1, x2}] <= y1 + 1)
ans++;
};
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (j != 0 && j != m - 1)
for (int i_ : {i1[i][j], i2[i][j]})
{
if (i_ == -1)
continue;
int x1 = i;
int x2 = i_;
if (x1 > x2)
swap(x1, x2);
check(x1, x2, j - 1, j2[x1 + 1][j - 1]);
check(x1, x2, j1[x1 + 1][j + 1], j + 1);
}
}
}
return ans;
}
// int main()
// {
// cout << count_rectangles({{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}) << endl;
// }
