#include "rect.h"
#include <iostream>
#include <stack>
#include <map>
using namespace std;
const int MAX_TAILLE = 2542, INF = 1e9;
int nbLigne, nbCol;
int grille[MAX_TAILLE][MAX_TAILLE];
void input() {
cin >> nbLigne >> nbCol;
for(int lig = 0; lig < nbLigne; lig++) {
for(int col = 0; col < nbCol; col++) {
cin >> grille[lig][col];
}
}
}
int segment[MAX_TAILLE][MAX_TAILLE][2][2];
int valide[MAX_TAILLE][MAX_TAILLE] = {0};
void algo1d(int direction, int pos) {
int limitePos2 = nbCol;
if(direction % 2 == 1)
limitePos2 = nbLigne;
stack<pair<int, int>> grandAvant;
grandAvant.push({-INF, INF});
for(int pos2 = 0; pos2 < limitePos2; pos2++) {
int vraiPos2 = pos2;
if(direction >= 2)
vraiPos2 = limitePos2 - 1 - pos2;
int valCur = grille[pos][vraiPos2];
if(direction % 2 == 1)
valCur = grille[vraiPos2][pos];
while(grandAvant.top().second <= valCur)
grandAvant.pop();
int extremite = grandAvant.top().first+1;
if(direction >= 2)
extremite -= 2;
//cout <<vraiPos2 << " " << pos << " " << extremite << " " << valCur<< endl;
if(direction % 2 == 0)
segment[pos][vraiPos2][0][direction/2] = extremite;
else
segment[vraiPos2][pos][1][direction/2] = extremite;
grandAvant.push({vraiPos2, valCur});
}
}
pair<int, int> prolonge[MAX_TAILLE][MAX_TAILLE];
void resetProlonge() {
for(int deb = 0; deb < MAX_TAILLE; deb++) {
for(int fin = 0; fin < MAX_TAILLE; fin++) {
prolonge[deb][fin] = {-1, 1};
}
}
}
int delta[2] = {-1, 1};
void balaieHorizontal(int direction) {
resetProlonge();
for(int lig = 0; lig < nbLigne; lig++) {
for(int col = 0; col < nbCol; col++) {
int posLig = lig;
if(direction == 1)
posLig = nbLigne - 1 - lig;
int debSeg = segment[posLig][col][0][0];
int finSeg = segment[posLig][col][0][1];
if(debSeg < 0 || finSeg < 0 || segment[posLig][col][1][0] < 0 || segment[posLig][col][1][1] < 0)
continue;
if(prolonge[debSeg][finSeg].first == posLig + delta[direction])
prolonge[debSeg][finSeg].second++;
else if(prolonge[debSeg][finSeg].first * delta[direction] > (posLig + delta[direction]) * delta[direction])
prolonge[debSeg][finSeg].second = 1;
prolonge[debSeg][finSeg].first = posLig;
//cout << posLig << " " << col << " " << debSeg << " " << finSeg << " " << prolonge[debSeg][finSeg].second << " " << segment[posLig][col][1][direction] << endl;
if(abs(segment[posLig][col][1][direction] - posLig) + 1 <= prolonge[debSeg][finSeg].second) {
valide[posLig][col]++;
}
}
}
}
void balaieVertical(int direction) {
resetProlonge();
for(int col = 0; col < nbCol; col++) {
for(int lig = 0; lig < nbLigne; lig++) {
int posCol = col;
if(direction == 1)
posCol = nbCol - col - 1;
int debSeg = segment[lig][posCol][1][0];
int finSeg = segment[lig][posCol][1][1];
if(debSeg < 0 || finSeg < 0 || segment[lig][posCol][0][0] < 0 || segment[lig][posCol][0][1] < 0)
continue;
if(prolonge[debSeg][finSeg].first == posCol + delta[direction])
prolonge[debSeg][finSeg].second++;
else if(prolonge[debSeg][finSeg].first * delta[direction] > (posCol + delta[direction]) * delta[direction])
prolonge[debSeg][finSeg].second = 1;
prolonge[debSeg][finSeg].first = posCol;
if(abs(segment[lig][posCol][0][direction] - posCol) + 1 <= prolonge[debSeg][finSeg].second) {
valide[lig][posCol]++;
}
}
}
}
int total = 0;
map<pair<pair<int, int>, pair<int, int>>, int> qui;
long long count_rectangles(std::vector<std::vector<int> > a) {
nbLigne = a.size();
nbCol = a[0].size();
for(int lig = 0; lig < nbLigne; lig++) {
for(int col = 0; col < nbCol; col++) {
grille[lig][col] = a[lig][col];
}
}
for(int lig = 0; lig < nbLigne; lig++) {
algo1d(0, lig);
algo1d(2, lig);
}
for(int col = 0; col < nbCol; col++) {
algo1d(1, col);
algo1d(3, col);
}
/*
for(int lig = 0; lig < nbLigne; lig++) {
for(int col = 0; col < nbCol; col++) {
cout << lig << " " << col << " " << segment[lig][col][0][0] << " " << segment[lig][col][0][1] << endl;
}
}
for(int lig = 0; lig < nbLigne; lig++) {
for(int col = 0; col < nbCol; col++) {
cout << lig << " " << col << " " << segment[lig][col][1][0] << " " << segment[lig][col][1][1] << endl;
}
}
*/
balaieHorizontal(0);
balaieHorizontal(1);
balaieVertical(0);
balaieVertical(1);
for(int lig = 0; lig < nbLigne; lig++) {
for(int col = 0; col < nbCol; col++) {
int gauche = segment[lig][col][0][0], droite = segment[lig][col][0][1];
int haut = segment[lig][col][1][0], bas = segment[lig][col][1][1];
//cout << lig << " " << col << " " << valide[lig][col] << endl;
if(valide[lig][col] == 4 && qui[{{gauche, droite}, {haut, bas}}] == 0) {
total++;
qui[{{gauche, droite}, {haut, bas}}] = 1;
}
}
}
return total;
}
