#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define sz(x) (int)x.size()
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
typedef signed i32;
typedef pair<int, int> ii;
typedef vector<i32> vi32;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vi32> vvi32;
typedef vector<vii> vvii;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
long long count_rectangles(vvi a)
{
int n = sz(a); // h
int m = sz(a[0]); // w
vvvb validUp(n, vvb(m, vb(m)));
vvvb validDown(n, vvb(m, vb(m)));
vvvb validL(m, vvb(n, vb(n)));
vvvb validR(m, vvb(n, vb(n))); // omwisselen voor cache friendlyness?
vvvi pSumValR(n, vvi(n, vi(m)));
for (int c = 1; c < m - 1; c++)
{
for (int r1 = 1; r1 < n - 1; r1++)
{
bool valL = 1;
bool valR = 1;
for (int r2 = r1; r2 < n - 1; r2++)
{
valL &= (a[r2][c] < a[r2][c - 1]);
valR &= (a[r2][c] < a[r2][c + 1]);
validL[c][r1][r2] = valL;
validR[c][r1][r2] = valR;
}
}
}
for (int r = 1; r < n - 1; r++)
{
for (int c1 = 1; c1 < m - 1; c1++)
{
bool valUp = 1;
bool valDown = 1;
for (int c2 = c1; c2 < m - 1; c2++)
{
valUp &= (a[r][c2] < a[r - 1][c2]);
valDown &= (a[r][c2] < a[r + 1][c2]);
validUp[r][c1][c2] = valUp;
validDown[r][c1][c2] = valDown;
}
}
}
for (int r1 = 1; r1 < n - 1; r1++)
{
for (int r2 = r1; r2 < n - 1; r2++)
{
for (int c = 1; c < m - 1; c++)
{
pSumValR[r1][r2][c] = pSumValR[r1][r2][c - 1] + (validR[c][r1][r2]);
}
}
}
long long res = 0;
for (int c = 1; c < m - 1; c++)
{
for (int r1 = 1; r1 < n - 1; r1++)
{
for (int r2 = r1; r2 < n - 1; r2++)
{
if (!validL[c][r1][r2])
break;
int lo = c, hi = m - 2;
int ans = -1;
while (hi >= lo)
{
int c2 = (lo + hi) / 2;
if (validUp[r1][c][c2] && validDown[r2][c][c2])
{
ans = c2;
lo = c2 + 1;
}
else
{
hi = c2 - 1;
}
}
if (ans == -1)
continue;
res += pSumValR[r1][r2][ans] - pSumValR[r1][r2][c - 1];
}
}
}
return res;
}
