#include "rect.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef pair<int, int> pii;
const int N = 2510;
struct Maximal {
vector<int> A, L, R;
void Add(int x){
A.pb(x);
}
void Init(){
sort(all(A));
A.resize( unique(all(A)) - A.begin());
L.resize(A.size(), 0);
for(int i = 1; i < (int) A.size(); i++)
L[i] = (A[i - 1] + 1 == A[i] ? L[i - 1] + 1 : 0);
R.resize(A.size(), 0);
for(int i = ((int)A.size()) - 2; i >= 0; i--)
R[i] = (A[i] + 1 == A[i + 1] ? R[i + 1] + 1 : 0);
}
pii Get(int x){
int idx = lower_bound(all(A), x) - A.begin();
assert(A[idx] == x);
return pii(L[idx], R[idx]);
}
};
Maximal row[N][N], col[N][N];
int L[N][N], R[N][N], U[N][N], D[N][N];
long long count_rectangles(vector< vector<int> > a){
int n = a.size();
int m = a[0].size();
for(int i = 0; i < N; i++){
fill(L[i], L[i] + N, -1);
fill(R[i], R[i] + N, m);
fill(U[i], U[i] + N, -1);
fill(D[i], D[i] + N, n);
}
vector<int> stk;
for(int i = 0; i < n; i++){
stk.clear();
for(int j = 0; j < m; j++){
while(!stk.empty() && a[i][stk.back()] <= a[i][j]){
R[i][stk.back()] = j;
stk.pop_back();
}
if(!stk.empty())
L[i][j] = stk.back();
stk.pb(j);
}
}
for(int j = 0; j < m; j++){
stk.clear();
for(int i = 0; i < n; i++){
while(!stk.empty() && a[stk.back()][j] <= a[i][j]){
D[stk.back()][j] = i;
stk.pop_back();
}
if(!stk.empty())
U[i][j] = stk.back();
stk.pb(i);
}
}
// debug("A");
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(L[i][j] != -1)
row[ L[i][j] ][j].Add(i);
if(R[i][j] != m)
row[j][ R[i][j] ].Add(i);
if(U[i][j] != -1)
col[ U[i][j] ][i].Add(j);
if(D[i][j] != n)
col[i][ D[i][j] ].Add(j);
}
}
// debug("B");
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
row[i][j].Init(), col[i][j].Init();
// debug("C");
vector< pair<pii, pii> > valid;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(L[i][j] == -1 || U[i][j] == -1 || R[i][j] == m || D[i][j] == n)
continue;
pii rw = pii(L[i][j], R[i][j]);
pii cl = pii(U[i][j], D[i][j]);
pii grw= row[rw.F][rw.S].Get(i);
pii gcl= col[cl.F][cl.S].Get(j);
if((i - grw.F <= cl.F + 1) && (cl.S -1 <= i + grw.S))
if((j - gcl.F <= rw.F + 1) && (rw.S - 1 <= j + gcl.S))
valid.pb({rw, cl});
}
}
sort(all(valid));
valid.resize( unique(all(valid)) - valid.begin() );
return valid.size();
}
