#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Nmax = 2505;
int go_up[Nmax][Nmax], go_down[Nmax][Nmax], go_left[Nmax][Nmax], go_right[Nmax][Nmax], h[Nmax][Nmax];
int dp_up[Nmax][Nmax], dp_down[Nmax][Nmax], dp_left[Nmax][Nmax], dp_right[Nmax][Nmax];
int n, m;
vector<int> pos[Nmax];
static void compute(vector<int> &v, vector<int> &go)
{
go.resize(v.size());
int i, nr = 0;
vector<int> st(v.size() + 1);
st[0] = -1;
for(i=0; i<v.size(); ++i)
{
while(nr && v[i] > v[st[nr]]) --nr;
go[i] = st[nr];
st[++nr] = i;
}
}
static void prec()
{
vector<int> aux, ans;
int i, j;
for(i=0; i<n; ++i)
{
aux.clear();
for(j=0; j<m; ++j) aux.push_back(h[i][j]);
compute(aux, ans);
for(j=0; j<m; ++j)
go_left[i][j] = ans[j];
reverse(aux.begin(), aux.end());
compute(aux, ans);
for(j=0; j<m; ++j)
go_right[i][j] = m-1-ans[m-j-1];
}
for(j=0; j<m; ++j)
{
aux.clear();
for(i=0; i<n; ++i) aux.push_back(h[i][j]);
compute(aux, ans);
for(i=0; i<n; ++i)
go_up[i][j] = ans[i];
reverse(aux.begin(), aux.end());
compute(aux, ans);
for(i=0; i<n; ++i)
go_down[i][j] = n-1-ans[n-i-1];
}
}
static void prec2()
{
int i, j;
for(j=m-1; j>=0; --j)
for(i=n-1; i>=0; --i)
{
if(j<m-1 && go_down[i][j+1] == go_down[i][j])
dp_down[i][j] = 1 + dp_down[i][j+1];
else if(j<m-1 && go_up[go_down[i][j]][j+1] == i) dp_down[i][j] = 1 + dp_up[go_down[i][j]][j+1];
else dp_down[i][j] = 1;
///
if(j<m-1 && go_up[i][j+1] == go_up[i][j])
dp_up[i][j] = 1 + dp_up[i][j+1];
else if(j<m-1 && go_down[go_up[i][j]][j+1] == i) dp_up[i][j] = 1 + dp_down[go_up[i][j]][j+1];
else dp_up[i][j] = 1;
}
for(i=n-1; i>=0; --i)
for(j=m-1; j>=0; --j)
{
///
if(i<n-1 && go_right[i+1][j] == go_right[i][j])
dp_right[i][j] = 1 + dp_right[i+1][j];
else if(i<n-1 && go_left[i+1][go_right[i][j]] == j) dp_right[i][j] = 1 + dp_left[i+1][go_right[i][j]];
else dp_right[i][j] = 1;
///
if(i<n-1 && go_left[i+1][j] == go_left[i][j])
dp_left[i][j] = 1 + dp_left[i+1][j];
else if(i<n-1 && go_right[i+1][go_left[i][j]] == j) dp_left[i][j] = 1 + dp_right[i+1][go_left[i][j]];
else dp_left[i][j] = 1;
}
}
static bool check(int x, int y, int n, int m)
{
if(!n || !m) return 0;
// cerr << "candidate: cell " << x << ' ' << y << " dim " << n << ' ' << m << '\n';
/// coltul stanga-sus in (x, y), dimensiune (n, m)
bool ok = 1;
if(go_down[x-1][y] == x+n)
ok &= (dp_down[x-1][y] >= m);
else if(go_up[x+n][y] == x-1) ok &= (dp_up[x+n][y] >= m);
else ok = 0;
if(go_right[x][y-1] == y+m)
ok &= (dp_right[x][y-1] >= n);
else if(go_left[x][y+m] == y-1) ok &= (dp_left[x][y+m] >= n);
else ok = 0;
// cerr << "answer: " << (int) ok << '\n';
// if(ok) cerr << "# " << "candidate: cell " << x << ' ' << y << " dim " << n << ' ' << m << '\n';
return ok;
}
ll solve()
{
int i, j;
int ans = 0;
for(i=1; i<n-1; ++i)
{
for(j=0; j<=m; ++j) pos[j].clear(); /// pos[j].shrink_to_fit();
for(j=0; j<m; ++j)
{
if(go_right[i][j] != m)
pos[j+1].push_back(go_right[i][j] - j - 1);
if(go_left[i][j] != -1 && h[i][j] != h[i][go_left[i][j]])
pos[go_left[i][j] + 1].push_back(j - go_left[i][j] - 1);
}
for(j=1; j<m-1; ++j)
{
if(go_down[i-1][j] == n) continue;
int N;
N = go_down[i-1][j] - i;
for(auto M : pos[j])
ans += check(i, j, N, M);
}
for(j=m-2; j>=1; --j)
{
if(go_up[i+1][j] == -1) continue;
if(h[i+1][j] == h[go_up[i+1][j]][j]) continue;
int N;
N = i - go_up[i+1][j];
for(auto M : pos[j])
ans += check(i-N+1, j, N, M);
}
}
return ans;
}
ll count_rectangles(vector<vector<int>> _h)
{
n = _h.size();
m = _h[0].size();
int i, j;
for(i=0; i<n; ++i)
for(j=0; j<m; ++j)
h[i][j] = _h[i][j];
prec();
prec2();
return solve();
}
