#include "rect.h"
//#include "grader.cpp"
#include <map>
#include <stack>
#include <deque>
#include <vector>
#include <assert.h>
#include <iostream>
#include <functional>
using namespace std;
const int MAXN = 2505;
const int MAXLog = 12;
struct FenwickTree
{
int n;
vector <int> tree;
FenwickTree(){}
FenwickTree(int n)
{
this->n = 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;
}
void reset(int newN)
{
n = newN;
for(int i = 0;i<=newN;i++) tree[i] = 0;
}
};
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];
short int downBad[MAXN][MAXN][20], upBad[MAXN][MAXN][20];
int logVal[MAXN];
void initSparse(short 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];
}
}
}
}
vector <int> pairRows[MAXN][MAXN];
FenwickTree T;
vector <int> toRemove[MAXN];
void init()
{
if(n<m) rotate90();
T = FenwickTree(n);
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);
}
for(int i = 1;i<n-1;i++)
{
vector <int> v;
for(int j = 0;j<m;j++)
{
for(int p = v.size()-1;p>=0;p--)
{
if(v[p]<leftBad[i][j]) break;
pairRows[ v[p] ][j].push_back(i);
}
while(v.empty()==false && a[i][v.back()]<=a[i][j]) v.pop_back();
v.push_back(j);
}
}
}
int getVal(int row, int l, int r, short 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]);
}
}
long long evalRowSeq(int lRow, int rRow, int c1, int c2)
{
if(lRow>rRow) return 0;
T.reset(rRow-lRow+1);
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-lRow, +1);
toRemove[getVal(row+1, c1+1, c2-1, upBad, 1)].push_back(row);
for(int x: toRemove[row]) T.update(x-lRow, -1);
ans += T.query(min(maxRow-1, rRow)-lRow);
}
return ans;
}
long long evalN3log()
{
long long answer = 0;
for(int c1 = 0;c1<m;c1++)
{
for(int c2 = c1+2;c2<m;c2++)
{
vector <int> v = pairRows[c1][c2];
if(v.empty()==true) continue;
for(int i = 0;i<v.size();)
{
int startInd = i;
for(;i<v.size();i++)
{
if(i-startInd!=v[i]-v[startInd]) break;
}
answer += evalRowSeq(v[startInd], v[i-1], c1, c2);
}
}
}
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();
}
/*
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
4 4
1 1 1 1
1 0 0 1
1 0 0 1
1 1 1 1
4 5
1 1 1 0 1
1 0 1 1 1
1 1 1 0 1
1 1 1 1 1
2 2
1 1
1 1
3 3
1 1 1
1 1 1
1 0 1
5 5
1 1 1 1 1
1 1 1 1 1
1 1 0 1 1
1 1 1 1 1
1 1 1 1 1
*/
