#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
vector<int> arr1[50001];
struct dir
{
int l,r,u,d;
int operator()()
{
return l+r*3+u*9+d*27;
}
};
dir ntd(int x)
{
int l = x%3;
x/=3;
int r = x%3;
x/=3;
int u = x%3;
x/=3;
int d = x%3;
x/=3;
return {l,r,u,d};
}
int* arr[50005];
int** pref[81];
int get_pref_sum(int x1, int y1, int x2, int y2, dir d)
{
if(x1 > x2 || y1 > y2) return 0;
int ind = d();
// cout << ind << " " << d.l << " " << d.r << " " << d.u << " " << d.d << " ind\n";
return pref[ind][x2][y2] - pref[ind][x2][y1-1] - pref[ind][x1-1][y2] + pref[ind][x1-1][y1-1];
}
pii get_best(int x, int y, dir d)
{
pair<int,pii> best;
//l
if(d.l != 0 && y-1 >= 0 && arr[x][y-1] < arr[x][y]) best = max(best,{arr[x][y-1],{x,y-1}});
if(d.r != 0 && arr[x][y+1] < arr[x][y]) best = max(best,{arr[x][y+1],{x,y+1}});
if(d.u != 0 && x-1 >= 0 && arr[x-1][y] < arr[x][y]) best = max(best,{arr[x-1][y],{x-1,y}});
if(d.d != 0 && arr[x+1][y] < arr[x][y]) best = max(best,{arr[x+1][y],{x+1,y}});
return best.ss;
}
int count_in(int x, int y, dir d)
{
int ans = 0;
if(d.l != 0)
{
pii b = get_best(x,y-1,{d.l-1,1,d.u,d.d});
if(b.ff == x && b.ss == y) ans++;
}
if(d.r != 0)
{
pii b = get_best(x,y+1,{1,d.r-1,d.u,d.d});
if(b.ff == x && b.ss == y) ans++;
}
if(d.u != 0)
{
pii b = get_best(x-1,y,{d.l,d.r,d.u-1,1});
if(b.ff == x && b.ss == y) ans++;
}
if(d.d != 0)
{
pii b = get_best(x+1,y,{d.l,d.r,1,d.d-1});
// cout << " \n" << b.ff << " " << b.ss << " b\n";
if(b.ff == x && b.ss == y) ans++;
}
// cout << ans << " ans\n";
if(ans == 0) return 1;
if(ans >= 2) return 2;
return 0;
}
bool* used_cor[50004];
vector<pii> dirs = {{0,1},{0,-1},{-1,0},{1,0}};
bool brut_force_rect(int x1, int y1, int x2, int y2)
{
pair<int,pii> best = {-1,{-1,-1}};
int path = 0;
rep2(x,x1,x2)
{
rep2(y,y1,y2) best = max(best,{arr[x][y],{x,y}});
}
pii cur = best.ss;
while(true)
{
path++;
best = {-1,{-1,-1}};
forall(it,dirs)
{
if(cur.ff + it.ff >= x1 && cur.ff + it.ff <= x2 && cur.ss+it.ss >= y1 && cur.ss+it.ss <= y2 && arr[cur.ff+it.ff][cur.ss+it.ss] < arr[cur.ff][cur.ss])
{
best = max(best,{arr[cur.ff+it.ff][cur.ss+it.ss],{it.ff+cur.ff,cur.ss+it.ss}});
}
}
if(best.ff == -1) break;
cur = best.ss;
}
return path == (x2-x1+1) * (y2-y1+1);
}
vector<pii> cor;
bool check_rect(int x1, int y1, int x2, int y2)
{
if((x2-x1+1) * (y2-y1+1) <= 20) return brut_force_rect(x1,y1,x2,y2);
int sum = get_pref_sum(x1+2,y1+2,x2-2,y2-2,{2,2,2,2});
// cout << x1 << " " << y1 << " " << x2 << " " << y2 << " xd1\n";
switch(x2-x1)
{
case 0:
{
sum += get_pref_sum(x1,y1+2,x1,y2-2,{2,2,0,0});
break;
}
case 1:
{
sum += get_pref_sum(x1,y1+2,x1,y2-2,{2,2,0,1});
sum += get_pref_sum(x1+1,y1+2,x1+1,y2-2,{2,2,1,0});
break;
}
case 2:
{
sum += get_pref_sum(x1,y1+2,x1,y2-2,{2,2,0,2});
sum += get_pref_sum(x1+1,y1+2,x1+1,y2-2,{2,2,1,1});
sum += get_pref_sum(x1+2,y1+2,x1+2,y2-2,{2,2,2,0});
break;
}
default:
{
sum += get_pref_sum(x1,y1+2,x1,y2-2,{2,2,0,2});
sum += get_pref_sum(x1+1,y1+2,x1+1,y2-2,{2,2,1,2});
sum += get_pref_sum(x2,y1+2,x2,y2-2,{2,2,2,0});
sum += get_pref_sum(x2-1,y1+2,x2-1,y2-2,{2,2,2,1});
break;
}
}
if(sum > 1) return 0;
// cout << " xd2\n";
switch(y2-y1)
{
case 0:
{
sum += get_pref_sum(x1+2,y1,x2-2,y1,{0,0,2,2});
break;
}
case 1:
{
sum += get_pref_sum(x1+2,y1,x2-2,y1,{0,1,2,2});
sum += get_pref_sum(x1+2,y1+1,x2-2,y1+1,{1,0,2,2});
break;
}
case 2:
{
sum += get_pref_sum(x1+2,y1,x2-2,y1,{0,2,2,2});
sum += get_pref_sum(x1+2,y1+1,x2-2,y1+1,{1,1,2,2});
sum += get_pref_sum(x1+2,y1+2,x2-2,y1+2,{2,0,2,2});
break;
}
default:
{
sum += get_pref_sum(x1+2,y1,x2-2,y1,{0,2,2,2});
sum += get_pref_sum(x1+2,y1+1,x2-2,y1+1,{1,2,2,2});
sum += get_pref_sum(x1+2,y2,x2-2,y2,{2,0,2,2});
sum += get_pref_sum(x1+2,y2-1,x2-2,y2-1,{2,1,2,2});
break;
}
}
// cout << " xd3\n";
// cout << sum << " first_sum\n";
if(sum > 1) return 0;
int corner_sum = 0;
cor = {};
rep2(i,0,1)
{
cor.pb({x1+i,y1});
cor.pb({x1+i,y1+1});
cor.pb({x1+i,y2});
cor.pb({x1+i,y2-1});
cor.pb({x2-i,y1});
cor.pb({x2-i,y1+1});
cor.pb({x2-i,y2});
cor.pb({x2-i,y2-1});
}
forall(it,cor)
{
if(it.ff >= x1 && it.ff <= x2 && it.ss >= y1 && it.ss <= y2 && !used_cor[it.ff][it.ss])
{
used_cor[it.ff][it.ss] = 1;
// cout << it.ff << " " << it.ss << " " << get_pref_sum(it.ff,it.ss,it.ff,it.ss,{min(2,it.ss-y1),min(2,y2-it.ss),min(2,it.ff-x1),min(2,x2-it.ff)}) << " " << count_in(it.ff,it.ss,{0,0,0,1}) << " cor\n";
corner_sum += get_pref_sum(it.ff,it.ss,it.ff,it.ss,{min(2,it.ss-y1),min(2,y2-it.ss),min(2,it.ff-x1),min(2,x2-it.ff)});
}
}
forall(it,cor)
{
if(it.ff >= x1 && it.ff <= x2 && it.ss >= y1 && it.ss <= y2)
{
used_cor[it.ff][it.ss] = 0;
}
}
return corner_sum + sum == 1;
}
int sumMap[1000004];
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//random_start();
int n,m;
cin >> n >> m;
rep2(i,1,n)
{
arr1[i].resize(m+1);
rep2(j,1,m) cin >> arr1[i][j];
}
if(n > m)
{
rep2(i,1,m)
{
arr[i] = new int[n+3];
rep2(j,1,n)
{
arr[i][j] = arr1[j][i];
}
}
arr[0] = new int[n+3];
arr[m+1] = new int[n+3];
arr[m+2] = new int[n+3];
swap(n,m);
}
else
{
rep2(i,1,n)
{
arr[i] = new int[m+3];
rep2(j,1,m)
{
arr[i][j] = arr1[i][j];
}
}
arr[0] = new int[m+3];
arr[n+1] = new int[m+3];
arr[n+2] = new int[m+3];
}
rep2(i,0,n+3)
{
used_cor[i] = new bool[m+3];
rep(j,m+3) used_cor[i][j] = 0;
}
rep(k,81)
{
pref[k] = new int*[n+3];
rep(i,n+3)
{
pref[k][i] = new int[m+3];
}
}
rep(k,81)
{
rep2(i,1,n)
{
rep2(j,1,m)
{
pref[k][i][j] = pref[k][i-1][j] + pref[k][i][j-1] - pref[k][i-1][j-1] + count_in(i,j,ntd(k));
}
}
}
int dod = n*m*2+6;
ll ans = 0;
dir d;
rep2(x1,1,n)
{
rep2(x2,x1,n)
{
vi used_sums;
rep2(y,1,m)
{
rep2(y2,y,min(m,y+2))
{
if(check_rect(x1,y,x2,y2)) ans++;
}
if(y < 4) continue;
y -= 3;
ll p_sum = 0;
switch(x2-x1)
{
case 0:
{
p_sum += get_pref_sum(x1,y,x1,y,{0,2,0,0});
p_sum += get_pref_sum(x1,y+1,x1,y+1,{1,2,0,0});
d = {2,2,0,0};
p_sum += - pref[d()][x1][y+1] + pref[d()][x1-1][y+1];
break;
}
case 1:
{
p_sum += get_pref_sum(x1,y,x1,y,{0,2,0,1});
p_sum += get_pref_sum(x1,y+1,x1,y+1,{1,2,0,1});
p_sum += get_pref_sum(x1+1,y,x1+1,y,{0,2,1,0});
p_sum += get_pref_sum(x1+1,y+1,x1+1,y+1,{1,2,1,0});
d = {2,2,0,1};
p_sum += - pref[d()][x1][y+1] + pref[d()][x1-1][y+1];
d = {2,2,1,0};
p_sum += - pref[d()][x1+1][y+1] + pref[d()][x1][y+1];
break;
}
case 2:
{
p_sum += get_pref_sum(x1,y,x1,y,{0,2,0,2});
p_sum += get_pref_sum(x1,y+1,x1,y+1,{1,2,0,2});
p_sum += get_pref_sum(x1+1,y,x1+1,y,{0,2,1,1});
p_sum += get_pref_sum(x1+1,y+1,x1+1,y+1,{1,2,1,1});
p_sum += get_pref_sum(x1+2,y,x1+2,y,{0,2,2,0});
p_sum += get_pref_sum(x1+2,y+1,x1+2,y+1,{1,2,2,0});
d = {2,2,0,2};
p_sum += - pref[d()][x1][y+1] + pref[d()][x1-1][y+1];
d = {2,2,1,1};
p_sum += - pref[d()][x1+1][y+1] + pref[d()][x1][y+1];
d = {2,2,2,0};
p_sum += - pref[d()][x1+2][y+1] + pref[d()][x1+1][y+1];
break;
}
default:
{
p_sum += get_pref_sum(x1,y,x1,y,{0,2,0,2});
p_sum += get_pref_sum(x1,y+1,x1,y+1,{1,2,0,2});
p_sum += get_pref_sum(x1+1,y,x1+1,y,{0,2,1,2});
p_sum += get_pref_sum(x1+1,y+1,x1+1,y+1,{1,2,1,2});
p_sum += get_pref_sum(x2,y,x2,y,{0,2,2,0});
p_sum += get_pref_sum(x2,y+1,x2,y+1,{1,2,2,0});
p_sum += get_pref_sum(x2-1,y,x2-1,y,{0,2,2,1});
p_sum += get_pref_sum(x2-1,y+1,x2-1,y+1,{1,2,2,1});
p_sum += get_pref_sum(x1+2,y,x2-2,y,{0,2,2,2});
p_sum += get_pref_sum(x1+2,y+1,x2-2,y+1,{1,2,2,2});
d = {2,2,2,0};
p_sum += - pref[d()][x2][y+1] + pref[d()][x2-1][y+1];
d = {2,2,2,1};
p_sum += -pref[d()][x2-1][y+1] + pref[d()][x2-2][y+1];
d = {2,2,0,2};
p_sum += -pref[d()][x1][y+1] + pref[d()][x1-1][y+1];
d = {2,2,1,2};
p_sum += -pref[d()][x1+1][y+1] + pref[d()][x1][y+1];
break;
}
}
if(x2-x1 > 3)
{
d = {2,2,2,2};
p_sum += -pref[d()][x2-2][y+1] + pref[d()][x1+1][y+1];
}
y+=3;
sumMap[p_sum+dod]++;
used_sums.pb(p_sum);
ll my_sum = 0;
switch(x2-x1)
{
case 0:
{
my_sum += get_pref_sum(x1,y,x1,y,{2,0,0,0});
my_sum += get_pref_sum(x1,y-1,x1,y-1,{2,1,0,0});
d = {2,2,0,0};
my_sum += pref[d()][x1][y-2] - pref[d()][x1-1][y-2];
break;
}
case 1:
{
my_sum += get_pref_sum(x1,y,x1,y,{2,0,0,1});
my_sum += get_pref_sum(x1,y-1,x1,y-1,{2,1,0,1});
my_sum += get_pref_sum(x1+1,y,x1+1,y,{2,0,1,0});
my_sum += get_pref_sum(x1+1,y-1,x1+1,y-1,{2,1,1,0});
d = {2,2,0,1};
my_sum += pref[d()][x1][y-2] - pref[d()][x1-1][y-2];
d = {2,2,1,0};
my_sum += pref[d()][x1+1][y-2] - pref[d()][x1][y-2];
break;
}
case 2:
{
my_sum += get_pref_sum(x1,y,x1,y,{2,0,0,2});
my_sum += get_pref_sum(x1,y-1,x1,y-1,{2,1,0,2});
my_sum += get_pref_sum(x1+1,y,x1+1,y,{2,0,1,1});
my_sum += get_pref_sum(x1+1,y-1,x1+1,y-1,{2,1,1,1});
my_sum += get_pref_sum(x1+2,y,x1+2,y,{2,0,2,0});
my_sum += get_pref_sum(x1+2,y-1,x1+2,y-1,{2,1,2,0});
d = {2,2,0,2};
my_sum += pref[d()][x1][y-2] - pref[d()][x1-1][y-2];
d = {2,2,1,1};
my_sum += pref[d()][x1+1][y-2] - pref[d()][x1][y-2];
d = {2,2,2,0};
my_sum += pref[d()][x1+2][y-2] - pref[d()][x1+1][y-2];
break;
}
default:
{
my_sum += get_pref_sum(x1,y,x1,y,{2,0,0,2});
my_sum += get_pref_sum(x1,y-1,x1,y-1,{2,1,0,2});
my_sum += get_pref_sum(x1+1,y,x1+1,y,{2,0,1,2});
my_sum += get_pref_sum(x1+1,y-1,x1+1,y-1,{2,1,1,2});
my_sum += get_pref_sum(x2,y,x2,y,{2,0,2,0});
my_sum += get_pref_sum(x2,y-1,x2,y-1,{2,1,2,0});
my_sum += get_pref_sum(x2-1,y,x2-1,y,{2,0,2,1});
my_sum += get_pref_sum(x2-1,y-1,x2-1,y-1,{2,1,2,1});
my_sum += get_pref_sum(x1+2,y,x2-2,y,{2,0,2,2});
my_sum += get_pref_sum(x1+2,y-1,x2-2,y-1,{2,1,2,2});
d = {2,2,2,0};
my_sum += pref[d()][x2][y-2] - pref[d()][x2-1][y-2];
d = {2,2,2,1};
my_sum += pref[d()][x2-1][y-2] - pref[d()][x2-2][y-2];
d = {2,2,0,2};
my_sum += pref[d()][x1][y-2] - pref[d()][x1-1][y-2];
d = {2,2,1,2};
my_sum += pref[d()][x1+1][y-2] - pref[d()][x1][y-2];
break;
}
}
if(x2-x1 > 3)
{
d = {2,2,2,2};
my_sum += pref[d()][x2-2][y-2] - pref[d()][x1+1][y-2];
}
ans += sumMap[1-my_sum+dod];
}
forall(it,used_sums)
{
sumMap[it+dod] = 0;
}
}
}
cout << ans << "\n";
}
