#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using fl = long double;
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template<typename S, typename T>
void xmin(S&a, T const&b){if(b<a) a=b;}
template<typename S, typename T>
void xmax(S&a, T const&b){if(b>a) a=b;}
template<bool enabled>
struct Debug{
template<typename S, typename T = void> struct Tag_Printable : false_type {};
template<typename S> struct Tag_Printable<S, decltype((void)(cerr << declval<S>()))> : true_type {};
template<typename S, typename T = void> struct Tag_Iterable: false_type {};
template<typename S> struct Tag_Iterable<S, decltype((void)(begin(declval<S>()), end(declval<S>())))> : true_type {};
template<typename T, size_t N> struct Tuple_Printer{
template<typename S>
static S& print(S& stream, T const&t){
return Tuple_Printer<T, N-1>::print(stream, t) << ", " << get<N>(t);
}
};
template<typename T> struct Tuple_Printer<T, 0>{
template<typename S>
static S& print(S& stream, T const&t){
return stream << get<0>(t);
}
};
template<typename T, typename... Args>
Debug& print(T const&x, true_type, Args...){
#ifdef LOCAL_RUN
if(enabled){
cerr << boolalpha << x;
}
#endif // LOCAL_RUN
return *this;
}
template<typename T>
Debug& print(T const&x, false_type, true_type){
*this << "[";
bool first = true;
for(auto &e:x){
if(!first) *this << ", ";
*this << e;
first = false;
}
return *this << "]";
}
template<typename S, typename T>
Debug& print(pair<S, T> const&x, false_type, false_type){
return *this << "(" << x.first << ", " << x.second << ")";
}
template<typename... Args>
Debug& print(tuple<Args...> const&t, false_type, false_type){
return Tuple_Printer<decltype(t), sizeof...(Args)-1>::print(*this, t);
}
template<typename T>
Debug& operator<<(T const&x){
return print(x, Tag_Printable<T>{}, Tag_Iterable<T>{});
}
};
Debug<true> debug;
// Debug<false> debug; // disable debug printing
#define named(x) string(#x) << " : " << x
// Preprocesses in O(n log n) to allow you to query
// the next larger element to the left/right in O(log n)
template<typename Key, typename Value, typename value_comp = less<Value>>
class Cartesian_Ancestors{
public:
// range maximum query in <n log n, 1>
template<typename T = Value, typename comp = value_comp>
class Sparsetable{
int compind(int i, int j, int l, int sign)const{
i = RMQ[lgn*i+l], j=RMQ[lgn*(j+sign*(1<<l))+l];
return comp()(data[i], data[j])? j : i;
}
int minind(int l, int r)const{
assert(l<r);
return compind(l, r, lg2[r-l],-1);
}
void build(){
lg2.resize(n+1);
for(int i=2;i<=n;++i) lg2[i]=1+lg2[i/2];
lgn = lg2.back()+1;
RMQ.resize(n*lgn);
for(int i=n-1;i>=0;--i){
RMQ[lgn*i]=i;
for(int j=0;j<lg2[n-i];++j) RMQ[lgn*i+j+1] = compind(i,i,j,1);
}
}
public:
Sparsetable() {}
Sparsetable(vector<T> v): n(v.size()), data(move(v)) { build(); }
/// max in [l, r)
pair<int, T const&> operator()(int const&i, int const&j){
int k = minind(i, j);
return pair<int, T const&>(k, data[k]);
}
int n, lgn;
vector<int> RMQ, lg2;
vector<T> data;
};
struct Ret{
int index;
Key key;
Value value;
bool found;
friend ostream& operator<<(ostream&o, Ret const&r){
return o << "(" << r.index << ", " << r.key << ", " << r.value << ", " << r.found << ")";
}
};
Cartesian_Ancestors(vector<Value> values) : n(values.size()), keys(n), data(move(values)), st(data){
iota(keys.begin(), keys.end(), Key{});
}
Cartesian_Ancestors(vector<Key> keys_, vector<Value> values) : n(keys.size()), keys(move(keys_)), data(move(values)), st(data){
assert(keys.size() == values.size());
assert(is_sorted(keys.begin(), keys.end()));
}
Cartesian_Ancestors(vector<pair<Key, Value> > const&v) : n(v.size()), keys(n), data(n) {
for(int i=0;i<n;++i){
tie(keys[i], data[i]) = v[i];
}
assert(is_sorted(keys.begin(), keys.end()));
st = Sparsetable<>(data);
}
template<bool allow_equal_key, bool allow_equal_value>
Ret right_larger(Key const&key, Value const& value){
auto it = allow_equal_key ? lower_bound(keys.begin(), keys.end(), key) : upper_bound(keys.begin(), keys.end(), key);
int i = it - keys.begin();
int l = i-1, r = n;
while(l+1 < r){
const int m = l + (r-l)/2;
auto x = st(i, m+1).second;
if(comp(x, value)){
l = m;
} else if(comp(value, x)){
r = m;
} else {
if(allow_equal_value){
r = m;
} else {
l = m;
}
}
}
return ret_from_index(r);
}
template<bool allow_equal_key, bool allow_equal_value>
Ret left_larger(Key const&key, Value const& value){
auto it = allow_equal_key ? upper_bound(keys.begin(), keys.end(), key) : lower_bound(keys.begin(), keys.end(), key);
int i = it - keys.begin();
int l = -1, r = i;
while(l+1 < r){
const int m = l + (r-l)/2;
auto x = st(m,i).second;
if(comp(x, value)){
r = m;
} else if(comp(value, x)){
l = m;
} else {
if(allow_equal_value){
l = m;
} else {
r = m;
}
}
}
return ret_from_index(l);
}
private:
Ret ret_from_index(int index){
if(index == -1 || index == n) return Ret{index, Key{}, Value{}, false};
return Ret{index, keys[index], data[index], true};
}
int n;
vector<Key> keys;
vector<Value> data;
Sparsetable<> st;
value_comp comp;
};
vector<vector<int> > transposed(vector<vector<int> > const&v){
const int n = v.size(), m = v.empty() ? 0 : v[0].size();
vector<vector<int> > ret(m, vector<int>(n));
for(int i=0;i<n;++i){
for(int j=0;j<m;++j){
ret[j][i] = v[i][j];
}
}
return ret;
}
struct Range_And{
Range_And(){}
Range_And(int Y_, vector<pair<int, int> > const&v) : Y(Y_), data(Y){
for(auto const&e:v){
data[e.second].emplace_back(e.first);
}
for(auto &e:data){
sort(e.begin(), e.end());
}
}
// all points present in {x} x [y1, y2)
bool all(int x, int y1, int y2) const {
auto it = lower_bound(data[x].begin(), data[x].end(), y1);
auto it2 = lower_bound(data[x].begin(), data[x].end(), y2);
return it2-it == y2-y1;
}
int Y;
vector<vector<int> > data;
};
vector<Range_And> build_ds(int X, vector<vector<pair<int, int> > > const&v){
vector<Range_And> ret;
for(auto const&e:v){
ret.emplace_back(X, e);
}
return ret;
}
// compute good ranges
vector<vector<pair<int, int> > > precalc(vector<vector<int> > const&v){
const int X = v.size(), Y = v[0].size();
vector<vector<pair<int, int> > > ret(Y);
for(int i=0;i<X;++i){
stack<pair<int, int> > s; // value, y
auto cand = [&](int y, int h){
while(!s.empty() && s.top().first <= h){
const int y2 = s.top().second;
ret[abs(y-y2)].emplace_back(i, min(y, y2));
s.pop();
}
s.emplace(h, y);
};
for(int j=0;j<Y;++j){
cand(j, v[i][j]);
}
while(!s.empty()) s.pop();
for(int j=Y-1;j>=0;--j){
cand(j, v[i][j]);
}
}
for(auto &e:ret){
sort(e.begin(), e.end());
e.erase(unique(e.begin(), e.end()), e.end());
}
return ret;
}
using Cart = Cartesian_Ancestors<int, int>;
ll count_rectangles(std::vector<std::vector<int> > a) {
const int X = a.size(), Y = a[0].size();
auto const row_ranges = precalc(a);
auto const row_ds = build_ds(Y, row_ranges);
auto const col_ranges = precalc(transposed(a));
auto const col_ds = build_ds(X, col_ranges);
debug << named(row_ranges) << "\n";
debug << named(col_ranges) << "\n";
vector<Cart> row_cart;
for(auto const&e:a){
row_cart.emplace_back(e);
}
vector<tuple<int, int, int, int> > ret;
auto add_rec = [&](int x1, int x2, int y1, int y2){
ret.emplace_back(x1, x2, y1, y2);
debug << "Rec: " << ret.back() << "\n";
};
for(int dx=2;dx<X;++dx){
for(auto const&u:col_ranges[dx]){
const int y = u.first, x = u.second;
// top left corner
if(y!=0){
auto const tmp = row_cart[x+1].right_larger<false, true>(y-1, a[x+1][y-1]);
if(dx == 2) debug << u << " " << named(tmp) << "\n";
if(tmp.found){
const int y2 = tmp.index;
const int dy = y2-y+1;
if(dy != 1){
if(col_ds[dx].all(x, y, y2) && row_ds[dy].all(y-1, x+1, x+dx)){
add_rec(x+1, x+dx-1, y, y2-1);
}
}
}
}
// top right corner
if(y+1 != Y){
auto const tmp = row_cart[x+1].left_larger<false, true>(y+1, a[x+1][y+1]);
if(tmp.found){
const int y2 = tmp.index;
const int dy = y-y2+1;
if(dy != 1){
if(col_ds[dx].all(x, y2+1, y+1) && row_ds[dy].all(y2, x+1, x+dx)){
add_rec(x+1, x+dx-1, y2+1, y);
}
}
}
}
}
}
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret.size();
}
