#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int NN = 6e5 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
#include "rect.h"
int n , m ;
vector < int > h[ 2505 ][ 2505 ] , w[ 2505 ][ 2505 ] ;
vector<vector<int> > a ;
void pot_build(){
FOR( i , n ){
int clos[ 2501 ] ;
stack < int > st ;
FOR( j , m ){
clos[ j ] = -1 ;
while( true ){
if( st.size() == 0 ) break ;
int x = st.top() ;
if( a[ i ][ x ] < a[ i ][ j ] ){
clos[ x ] = j ; st.pop() ;
} else break ;
}
st.push( j ) ;
}
FOR( j , m ){
int lst = j + 1 ;
while( true ){
if( lst >= m || lst == -1 ) break ;
int nx = clos[ lst ] ;
if( a[ i ][ lst ] >= a[ i ][ j ] ) break ;
if( nx != -1 ) w[ j ][ nx ].pb( i ) ;
lst = nx ;
}
}
}
// now for the horizontal ones
FOR( j , m ){
int clos[ 2501 ] ; stack < int > st ;
FOR( i , n ){
clos[ i ] = -1 ;
while( true ){
if( st.size() == 0 ) break ;
int x = st.top() ;
if( a[ x ][ j ] < a[ i ][ j ] ){
clos[ x ] = i ; st.pop() ;
} else break ;
}
st.push( i ) ;
}
FOR( i , n ){
int lst = i + 1 ;
while( true ){
if( lst >= n || lst == -1 ) break ;
int nx = clos[ lst ] ;
if( a[ lst ][ j ] >= a[ i ][ j ] ) break ;
if( nx != -1 ) h[ i ][ nx ].pb( j ) ;
lst = nx ;
}
}
}
}
struct W{
int l , high ;
};
struct H{
int high , l ;
};
vector < W > ww[ 2505 ][ 2505 ] ;
vector < H > hh[ 2505 ][ 2505 ] ;
void make_potential_sides(){
FOR( j , m ){
for( int j1 = j + 1 ; j1 < m ; j1 ++ ){
if( w[ j ][ j1 ].size() == 0 ) continue ;
int lst = w[ j ][ j1 ][ 0 ] ;
int fr = w[ j ][ j1 ][ 0 ] ;
for( int ps = 1 ; ps < w[ j ][ j1 ].size() ; ps ++ ){
if( w[ j ][ j1 ][ ps ] - 1 != lst ){
// push for future
W cur ; cur.l = j , cur.high = fr ;
for( int kk = fr ; kk <= lst ; kk ++ ) ww[ kk ][ j1 ].pb( cur ) ;
// make for new
fr = w[ j ][ j1 ][ ps ] ;
lst = w[ j ][ j1 ][ ps ] ;
}
else lst = w[ j ][ j1 ][ ps ] ;
}
// push for future
W cur ; cur.l = j , cur.high = fr ;
for( int kk = fr ; kk <= lst ; kk ++ ) ww[ kk ][ j1 ].pb( cur ) ;
w[ j ][ j1 ].clear() ;
}
}
// now for horizontals
FOR( i , n ){
for( int i1 = i + 1 ; i1 < n ; i1 ++ ){
if( h[ i ][ i1 ].size() == 0 ) continue ;
int lst = h[ i ][ i1 ][ 0 ] ;
int fr = h[ i ][ i1 ][ 0 ] ;
for( int ps = 1 ; ps < h[ i ][ i1 ].size() ; ps ++ ){
if( h[ i ][ i1 ][ ps ] - 1 != lst ){
// push for future
H cur ; cur.high = i , cur.l = fr ;
for( int kk = fr ; kk <= lst ; kk ++ ) hh[ i1 ][ kk ].pb( cur ) ;
// make for new
fr = h[ i ][ i1 ][ ps ] ;
lst = h[ i ][ i1 ][ ps ] ;
}
else lst = h[ i ][ i1 ][ ps ] ;
}
// push for future
H cur ; cur.high = i , cur.l = fr ;
for( int kk = fr ; kk <= lst ; kk ++ ) hh[ i1 ][ kk ].pb( cur ) ;
h[ i ][ i1 ].clear() ;
}
}
}
// sort to make the problem solvable
bool sortbyw( W a , W b ){
return a.high > b.high ;
}
bool sortbyh( H a , H b ){
return a.high > b.high ;
}
// get the sum ==> number of intersections
int fen[ 3000 ] ;
void add( int pos , int val ){
pos ++ ;
for( int j = pos ; j < 3000 ; j = j + ( j & ( - j ) ) ) fen[ j ] += val ;
}
int get( int l , int r ){
l ++ , r ++ ;
int sum = 0 ;
for( int j = r ; j > 0 ; j = j - ( j & ( - j ) ) ) sum += fen[ j ] ;
for( int j = l - 1 ; j > 0 ; j = j - ( j & ( - j ) ) ) sum -= fen[ j ] ;
return sum ;
}
long long count_rectangles(vector<vector<int> > A){
n = A.size() , m = A[ 0 ].size() ; a = A ;
pot_build() ;
make_potential_sides() ;
FOR( i , n ) FOR( j , m ){
sort( ww[ i ][ j ].begin() , ww[ i ][ j ].end() , sortbyw ) ;
sort( hh[ i ][ j ].begin() , hh[ i ][ j ].end() , sortbyh ) ;
}
// now calculate the answer
ll ans = 0 ;
FOR( i , n ){
FOR( j , m ){
// consider this as the low right spot
if( j == 0 || i == 0 ) continue ;
int pos = 0 ;
// cout << get( 0 , m ) << endl ;
for( auto x : ww[ i - 1 ][ j ] ){
add( x.l , 1 ) ;
}
for( auto x : hh[ i ][ j - 1 ] ){
while( true ){
if( pos == ww[ i - 1 ][ j ].size() ) break ;
if( ww[ i - 1 ][ j ][ pos ].high <= x.high + 1 ) break ;
add( ww[ i - 1 ][ j ][ pos ].l , -1 ) ;
pos ++ ;
}
ans = ans + get( x.l - 1 , j - 2 ) ;
}
// cout << i << " " << j << " " << ans << endl ;
// cout << ww[ i - 1 ][ j ].size() << " " << hh[ i ][ j - 1 ].size() << endl ;
for( ; pos < ww[ i - 1 ][ j ].size() ; pos ++ ){
add( ww[ i - 1 ][ j ][ pos ].l , -1 ) ;
}
}
}
return ans ;
}
// static const int buf_size = 4096;
// inline int getChar() {
// static char buf[buf_size];
// static int len = 0, pos = 0;
// if (pos == len) {
// pos = 0;
// len = fread(buf, 1, buf_size, stdin);
// }
// if (pos == len)
// return -1;
// return buf[pos++];
// }
// inline int readChar() {
// int c = getChar();
// while (c <= 32)
// c = getChar();
// return c;
// }
// inline int readInt() {
// int s = 1, c = readChar();
// int x = 0;
// while ('0' <= c && c <= '9') {
// x = x * 10 + c - '0';
// c = getChar();
// }
// return x;
// }
// int main() {
// cin >> n ;
// cin >> m ;
// vector<vector<int> > a(n, vector<int>(m));
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// a[i][j] = readInt();
// }
// }
// fclose(stdin);
// long long result= count_rectangles(a);
// printf("%lld\n", result);
// fclose(stdout);
// return 0;
// }
