#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long count_rectangles (std::vector<std::vector<int> > a) {
ll n = a.size ();
ll m = a[0].size ();
vector < vector < vector < ll > > >
ra (n, vector < vector < ll > > (m, vector < ll > (m))),
ca (m, vector < vector < ll > > (n, vector < ll > (n)));
for (ll k = 0; k < n; ++k)
for (ll i = 0; i < m; ++i)
{
int mx = 0;
for (ll j = i + 2; j < m; ++j)
{
mx = max (mx, a[k][j - 1]);
if (mx < a[k][i] && mx < a[k][j]) ra[k][i + 1][j - 1] = 1;
}
}
for (ll k = 0; k < m; ++k)
for (ll i = 0; i < n; ++i)
{
int mx = 0;
for (ll j = i + 2; j < n; ++j)
{
mx = max (mx, a[j - 1][k]);
if (mx < a[i][k] && mx < a[j][k]) ca[k][i + 1][j - 1] = 1;
}
}
for (ll i = 1; i < n; ++i)
for (ll j = 0; j < m; ++j)
for (ll k = 0; k < m; ++k)
ra[i][j][k] += ra[i - 1][j][k];
for (ll i = 1; i < m; ++i)
for (ll j = 0; j < n; ++j)
for (ll k = 0; k < n; ++k)
ca[i][j][k] += ca[i - 1][j][k];
auto alp = [&] (auto &x, int a, int b, int c, int d)
{
return (x[d][a][b] - (c ? x[c - 1][a][b] : 0)) == d - c + 1;
};
int c = 0;
for (ll i1 = 0; i1 < n; ++i1)
for (ll i2 = i1; i2 < n; ++i2)
for (ll j1 = 0; j1 < m; ++j1)
for (ll j2 = j1; j2 < m; ++j2)
if (alp (ca, i1, i2, j1, j2) && alp (ra, j1, j2, i1, i2))
++c;
return c;
}
