#include "rect.h"
//#include "grader.cpp"
#include <stack>
#include <deque>
#include <vector>
#include <assert.h>
#include <iostream>
using namespace std;
const int MAXN = 2505;
const int MAXLog = 15;
struct FenwickTree
{
vector <int> tree;
FenwickTree(){}
FenwickTree(int n)
{
this->tree.assign(n+5, 0);
}
void update(int ind, int val)
{
ind++;
while(ind<tree.size())
{
tree[ind] += val;
ind += ind&(-ind);
}
}
int query(int ind)
{
ind++;
int sum = 0;
while(ind>0)
{
sum += tree[ind];
ind -= ind&(-ind);
}
return sum;
}
};
int n, m;
int a[MAXN][MAXN];
int helpRotate[MAXN][MAXN];
void rotate90()
{
for(int j = 0;j<m;j++)
for(int i = n-1;i>=0;i--)
helpRotate[j][n - 1 - i] = a[i][j];
swap(n, m);
for(int i = 0;i<n;i++)
for(int j = 0;j<m;j++)
a[i][j] = helpRotate[i][j];
}
int rightBad[MAXN][MAXN], leftBad[MAXN][MAXN];
int downBad[MAXN][MAXN][20], upBad[MAXN][MAXN][20];
int logVal[MAXN];
void initSparse(int sparse[MAXN][MAXN][20], int row, int mode)
{
for(int step = 1;step<=MAXLog;step++)
{
for(int j = 0;j<m;j++)
{
if(j+(1<<(step-1))<m)
{
if(mode==0)
sparse[row][j][step] = min(sparse[row][j][step-1], sparse[row][j+(1<<(step-1))][step-1]);
else
sparse[row][j][step] = max(sparse[row][j][step-1], sparse[row][j+(1<<(step-1))][step-1]);
}
else
{
sparse[row][j][step] = sparse[row][j][step-1];
}
}
}
}
void init()
{
//if(n<m) rotate90();
logVal[0] = logVal[1] = 0;
for(int i = 2;i<=max(n, m)+2;i++)
{
logVal[i] = logVal[i/2] + 1;
}
for(int i = 0;i<n;i++)
{
stack <int> st;
for(int j = 0;j<m;j++)
{
while(st.empty()==false && a[i][st.top()]<a[i][j]) st.pop();
leftBad[i][j] = ((st.empty()==true)?-1:st.top());
st.push(j);
}
while(st.empty()==false) st.pop();
for(int j = m-1;j>=0;j--)
{
while(st.empty()==false && a[i][st.top()]<a[i][j]) st.pop();
rightBad[i][j] = ((st.empty()==true)?m-1:st.top());
st.push(j);
}
}
for(int j = 0;j<m;j++)
{
stack <int> st;
for(int i = 0;i<n;i++)
{
while(st.empty()==false && a[st.top()][j]<a[i][j]) st.pop();
upBad[i][j][0] = ((st.empty()==true)?-1:st.top());
st.push(i);
}
while(st.empty()==false) st.pop();
for(int i = n-1;i>=0;i--)
{
while(st.empty()==false && a[st.top()][j]<a[i][j]) st.pop();
downBad[i][j][0] = ((st.empty()==true)?n-1:st.top());
st.push(i);
}
}
for(int row = 0;row<n;row++)
{
initSparse(downBad, row, 0);
initSparse(upBad, row, 1);
}
}
int getVal(int row, int l, int r, int sparse[MAXN][MAXN][20], int mode)
{
int log2 = logVal[r-l+1];
if(mode==0)
{
if(l>r) return n;
return min(sparse[row][l][log2], sparse[row][r-(1<<log2)+1][log2]);
}
else
{
if(l>r) return -1;
return max(sparse[row][l][log2], sparse[row][r-(1<<log2)+1][log2]);
}
}
vector <int> toRemove[MAXN];
long long evalRowSeq(int lRow, int rRow, int c1, int c2)
{
if(lRow>rRow) return 0;
FenwickTree T(n);
for(int row = rRow;row>=lRow;row--)
{
toRemove[row].clear();
}
int ans = 0;
for(int row = rRow;row>=lRow;row--)
{
int maxRow = getVal(row-1, c1+1, c2-1, downBad, 0);
T.update(row, +1);
toRemove[getVal(row+1, c1+1, c2-1, upBad, 1)].push_back(row);
for(int x: toRemove[row]) T.update(x, -1);
ans += T.query(min(maxRow-1, rRow));
//if(c1==0 && c2==2) cout << "add " << row << " until " << getVal(row+1, c1+1, c2-1, upBad, 1) << '\n';
}
return ans;
}
long long evalN3log()
{
long long answer = 0;
for(int c1 = 0;c1<m;c1++)
{
for(int c2 = c1+2;c2<m;c2++)
{
int ind = 1;
while(ind<n-1)
{
int l = ind;
while(ind<n-1 && rightBad[ind][c1]>=c2 && leftBad[ind][c2]<=c1) ind++;
answer += evalRowSeq(l, ind-1, c1, c2);
ind++;
}
}
}
return answer;
}
long long count_rectangles(vector<vector<int>> _a)
{
n = _a.size();
m = _a[0].size();
for(int i = 0;i<n;i++)
for(int j = 0;j<m;j++)
a[i][j] = _a[i][j];
init();
return evalN3log();
/*
cout << '\n';
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++) cout << a[i][j] << " ";
cout << '\n';
}
cout << '\n';
cout << '\n';
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++) cout << downBad[i][j][0] << " ";
cout << '\n';
}
cout << '\n';
*/
}
/*
6 5
4 8 7 5 6
7 4 10 3 5
9 7 20 14 2
9 14 7 3 6
5 7 5 2 7
4 5 13 5 6
*/
