#include "rect.h"
#define pb push_back
using namespace std;
const int maxn = 3e3 + 10;
int n, m;
int is[maxn], pref[maxn];
int arr[maxn];
int t[maxn * 4];
void build(int i, int l, int r)
{
if(l == r)
{
t[i] = arr[l];
return;
}
int mid = (l + r)/2;
build(2*i, l, mid);
build(2*i+1, mid+1, r);
t[i] = max(t[2*i], t[2*i+1]);
}
int ql, qr;
int query(int i, int l, int r)
{
if(qr < l || ql > r)return 0;
if(ql <= l && r <= qr)return t[i];
int mid = (l + r)/2;
return max(query(2*i, l, mid), query(2*i+1, mid+1, r));
}
long long count_rectangles(std::vector<std::vector<int> > a)
{
n = a.size();
m = a[0].size();
for (int i = 0; i < m; ++ i)
{
arr[i] = a[1][i];
}
if(n < 3)return 0;
build(1, 1, m-2);
for (int i = 0; i < m; ++ i)
{
if(a[1][i] < a[0][i] && a[1][i] < a[2][i])is[i] = 1;
}
for (int i = 1; i < m; ++ i)
pref[i] = pref[i-1] + is[i];
int ans = 0;
for (int lt = 1; lt < m-1; ++ lt)
{
for (int rt = lt; rt < m-1; ++ rt)
{
int onl = lt - 1;
int onr = rt + 1;
ql = lt;
qr = rt;
int mx = query(1, 1, m-2);
int cntis = pref[rt] - pref[lt-1];
if(cntis == rt - lt + 1 && mx < min(a[1][onl], a[1][onr]))
ans ++;
}
}
return ans;
}
