#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
long long count_rectangles(vector<vector<int>> a)
{
int n=a.size(), m=a[0].size();
vector<short> iv[n][n];
for (int i=0;i<n;i++)
{
for (int j=0,mx=0;j<m;mx=0,j++)
for (int k=i+1;k+1<n;k++)
{
mx=max(mx,a[k][j]);
if (mx>=min(a[i][j],a[k+1][j]))
iv[i+1][k].push_back(j);
}
for (int k=i+1;k<n;k++)
iv[i+1][k].push_back(m), iv[i+1][k].shrink_to_fit();
}
bool val[n][m][m]={};
for (int i=0;i<n;i++)
for (int j=0,mx=0;j<m;j++,mx=0)
for (int k=j+1;k+1<m;k++)
{
mx=max(mx,a[i][k]);
if (mx<min(a[i][j],a[i][k+1])) val[i][j][k+1]=1;
}
long long ans=0;
for (int i=1;i<n-1;i++)
for (int j=0;j<m;j++)
for (int k=j+2;k<m;k++)
{
for (int l=i;l+1<n;l++)
{
if (!val[l][j][k]) break;
int x=upper_bound(iv[i][l].begin(), iv[i][l].end(), j)-begin(iv[i][l]);
if (iv[i][l][x]>=k)
ans++;
}
}
return ans;
}
