#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef pair<int,int> ii;
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vll>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 2510;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 13;
const int off = 1 << logo;
const int trsz = off << 1;
struct rmq{
vector<int> v;
int n;
static const int b = 30; // block size
int type;
vector<int> mask, t; // mask and sparse table
int op(int x, int y){
if(type == 0){
if(v[x] > v[y]) return x;
return y;
}
if(v[x] < v[y]) return x;
return y;
}
// least significant set bit
int lsb(int x) {
return x & -x;
}
// index of the most significant set bit
int msb_index(int x) {
return __builtin_clz(1)-__builtin_clz(x);
}
// answer query of v[r-size+1..r] using the masks, given size <= b
int small(int r, int size = b) {
// get only 'size' least significant bits of the mask
// and then get the index of the msb of that
int dist_from_r = msb_index(mask[r] & ((1<<size)-1));
return r - dist_from_r;
}
rmq(){
v = {};
n = 0;
type = 0;
mask = {};
t = {};
}
rmq(const vector<int> &v_, int _type){
v = v_;
n = v.size();
type = _type;
mask.clear();
mask.resize(n);
t.clear();
t.resize(n);
int curr_mask = 0;
for (int i = 0; i < n; i++) {
// shift mask by 1, keeping only the 'b' least significant bits
curr_mask = (curr_mask<<1) & ((1<<b)-1);
while (curr_mask > 0 and op(i, i - msb_index(lsb(curr_mask))) == i) {
// current value is smaller than the value represented by the
// last 1 in curr_mask, so we need to turn off that bit
curr_mask ^= lsb(curr_mask);
}
// append extra 1 to the mask
curr_mask |= 1;
mask[i] = curr_mask;
}
// build sparse table over the n/b blocks
// the sparse table is linearized, so what would be at
// table[j][i] is stored in table[(n/b)*j + i]
for (int i = 0; i < n/b; i++) t[i] = small(b*i+b-1);
for (int j = 1; (1<<j) <= n/b; j++) for (int i = 0; i+(1<<j) <= n/b; i++)
t[n/b*j+i] = op(t[n/b*(j-1)+i], t[n/b*(j-1)+i+(1<<(j-1))]);
}
// query(l, r) returns the actual minimum of v[l..r]
// to get the index, just change the first and last lines of the function
int query(int l, int r) {
// query too small
if (r-l+1 <= b) return v[small(r, r-l+1)];
// get the minimum of the endpoints
// (there is no problem if the ranges overlap with the sparse table query)
int ans = op(small(l+b-1), small(r));
// 'x' and 'y' are the blocks we need to query over
int x = l/b+1, y = r/b-1;
if (x <= y) {
int j = msb_index(y-x+1);
ans = op(ans, op(t[n/b*j+x], t[n/b*j+y-(1<<j)+1]));
}
return v[ans];
}
}h1[MAXN], h2[MAXN], h3[MAXN], h4[MAXN];
ii st[MAXN];
int bg[MAXN][MAXN][4];
vi veci[MAXN][2], vecj[MAXN][2];
ll count_rectangles(matrix mat){
int n = mat.size();
int m = mat[0].size();
int ind = 0;
REP(i, n){
st[0] = {inf, -1};
ind = 0;
REP(j, m){
while(st[ind].X < mat[i][j]) ind--;
bg[i][j][0] = st[ind].Y;
vecj[j][0].PB(bg[i][j][0]);
while(st[ind].X <= mat[i][j]) ind--;
bg[i][j][0] = st[ind].Y;
ind++;
st[ind] = {mat[i][j], j};
}
st[0] = {inf, m + 1};
ind = 0;
for(int j = m - 1; j >= 0; j--){
while(st[ind].X < mat[i][j]) ind--;
bg[i][j][1] = st[ind].Y;
vecj[j][1].PB(bg[i][j][1]);
while(st[ind].X <= mat[i][j]) ind--;
bg[i][j][1] = st[ind].Y;
ind++;
st[ind] = {mat[i][j], j};
}
}
REP(j, m){
st[0] = {inf, -1};
ind = 0;
REP(i, n){
while(st[ind].X < mat[i][j]) ind--;
bg[i][j][2] = st[ind].Y;
veci[i][0].PB(bg[i][j][2]);
while(st[ind].X <= mat[i][j]) ind--;
ind++;
st[ind] = {mat[i][j], i};
}
st[0] = {inf, n + 1};
ind = 0;
for(int i = n - 1; i >= 0; i--){
while(st[ind].X < mat[i][j]) ind--;
bg[i][j][3] = st[ind].Y;
veci[i][1].PB(bg[i][j][3]);
while(st[ind].X <= mat[i][j]) ind--;
bg[i][j][3] = st[ind].Y;
ind++;
st[ind] = {mat[i][j], i};
}
}
REP(j, m){
h1[j] = rmq(vecj[j][0], 0);
h2[j] = rmq(vecj[j][1], 1);
}
REP(i, n){
h3[i] = rmq(veci[i][0], 0);
h4[i] = rmq(veci[i][1], 1);
}
vll good;
REP(i, n){
REP(j, m){
if(i == 0 or j == 0 or i == n - 1 or j == m - 1) continue;
if(bg[i][j][0] == -1 or bg[i][j][1] == m + 1) continue;
if(bg[i][j][2] == -1 or bg[i][j][3] == n + 1) continue;
ll hash = 0;
REP(k, 4) hash *= MAXN, hash += bg[i][j][k];
if(bg[i][j][0] < h1[bg[i][j][1]].query(bg[i][j][2] + 1, (bg[i][j][3] - 1))) continue;
if(bg[i][j][1] > h2[bg[i][j][0]].query(bg[i][j][2] + 1, (bg[i][j][3] - 1))) continue;
if(bg[i][j][2] < h3[bg[i][j][3]].query(bg[i][j][0] + 1, (bg[i][j][1] - 1))) continue;
if(bg[i][j][3] > h4[bg[i][j][2]].query(bg[i][j][0] + 1, (bg[i][j][1] - 1))) continue;
good.PB(hash);
}
}
if(good.empty()) return 0;
sort(all(good));
ll pre = good[0];
int ret = 1;
for(auto &x : good) ret += (x != pre), pre = x;
return ret;
}
