#include "rect.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=702;
const int maxk=11;
set<int>col[maxn], lin[maxn];
int v[maxn][maxn], val[maxn][maxn], sp[maxn][maxn], ma_lin_dir[maxn][maxn][maxk], ma_lin_esq[maxn][maxn][maxk], ma_col_dir[maxn][maxn][maxk], ma_col_esq[maxn][maxn][maxk];
ll count_rectangles(vector<vector<int> > a){
int n=a.size(), m=a[0].size();
vector<pair<int,pair<int,int>>>process;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
val[i+1][j+1]=a[i][j];
col[j+1].insert(i+1);
lin[i+1].insert(j+1);
col[j+1].insert(0); col[j+1].insert(maxn);
lin[i+1].insert(0); lin[i+1].insert(maxn);
process.push_back({a[i][j],{i+1,j+1}});
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ma_lin_dir[i][j][0]=val[i][j+1];
ma_lin_esq[i][j][0]=val[i][j-1];
ma_col_dir[j][i][0]=val[i+1][j];
ma_col_esq[j][i][0]=val[i-1][j];
}
}
for(int i=1;i<=n;i++){
for(int k=1;k<maxk;k++){
for(int j=1;j<=m;j++){
int l=max(1,j-(1<<(k-1))), r=min(n,j+(1<<(k-1)));
ma_lin_dir[i][j][k]=max(ma_lin_dir[i][j][k-1],ma_lin_dir[i][r][k-1]);
ma_lin_esq[i][j][k]=max(ma_col_esq[i][j][k-1],ma_lin_esq[i][l][k-1]);
}
}
}
for(int j=1;j<=m;j++){
for(int k=1;k<maxk;k++){
for(int i=1;i<=n;i++){
int l=max(1,i-(1<<(k-1))), r=min(n,i+(1<<(k-1)));
ma_col_dir[j][i][k]=max(ma_col_dir[j][i][k-1],ma_col_dir[j][r][k-1]);
ma_col_esq[j][i][k]=max(ma_col_esq[j][i][k-1],ma_col_esq[j][l][k-1]);
}
}
}
sort(process.begin(),process.end()); reverse(process.begin(),process.end());
ll resp=0;
while(process.size()){
set<pair<pair<int,int>,pair<int,int>>>ans;
int at=process.back().first;
vector<pair<int,int>>aux;
vector<int>att;
while(process.size()&&process.back().first==at){
pair<int,int>p=process.back().second;
aux.push_back(p);
v[p.first][p.second]++;
att.push_back(p.first);
lin[p.first].erase(p.second); col[p.second].erase(p.first);
process.pop_back();
}
for(int x : att)
for(int i=1;i<=m;i++) sp[x][i]=sp[x][i-1]+v[x][i];
for(pair<int,int> p : aux){
int x=p.first, y=p.second;
int l1, l2, c1, c2;
auto f=lin[x].upper_bound(y), g=col[y].upper_bound(x);
l2=*g; c2=*f;
f--; g--;
l1=*g; c1=*f;
if(l1==0||c1==0||l2==maxn||c2==maxn) continue;
l1++; c1++; l2--; c2--;
bool ok=true;
int qtd=c2-c1+1, alt=l2-l1+1;
int k1=0, k2=0;
while((1<<k1)<=qtd) k1++;
while((1<<k2)<=alt) k2++;
k1--; k2--;
//cout << l1 << " " << c1 << " " << l2 << " " << c2 << endl;
for(int i=l1;i<=l2;i++) if(sp[i][c2]-sp[i][c1-1]!=qtd) ok=false;
for(int i=l1;i<=l2;i++){
int at=max(ma_lin_dir[i][c1-1][k1],ma_lin_esq[i][c2+1][k1]);
//cout << "lin " << i << " " << at << endl;
if(at>=min(val[i][c1-1],val[i][c2+1])) ok=false;
}
for(int i=c1;i<=c2;i++){
int at=max(ma_col_dir[i][l1-1][k2],ma_col_esq[i][l2+1][k2]);
//cout << "col " << i << " " << at << endl;
if(at>=min(val[l1-1][i],val[l2+1][i])) ok=false;
}
//cout << ok << endl << endl;
if(ok) ans.insert({{l1,c1},{l2,c2}});
}
//for(pair<pair<int,int>,pair<int,int>> p : ans) cout << p.first.first << " " << p.first.second << " " << p.second.first << " " << p.second.second << endl;
resp+=ans.size();
/*for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cout << v[i][j] << " ";
cout << endl;
}
cout << resp << endl << endl;*/
}
return resp;
}
