#ifdef LOCAL
#define _GLIBCXX_DEBUG
#else

#endif

#include <bits/stdc++.h>

#include "rect.h"

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(234);
const ll inf = 1e18;

int n, m;
vector<vector<int>> a;
vector<vector<vector<int>>> gor, god, gor_dpth, god_dpth;

void build_go(vector<int> &f, vector<vector<int>> &go) {
    int n = f.size();
    go.assign(n, vector<int>());
    vector<pair<int, int>> stck;
    stck.reserve(n);
    for (int i = 0; i < n; i += 1) {
        while (!stck.empty() && stck.back().first < f[i]) {
            stck.pop_back();
        }
        if (!stck.empty() && stck.back().second != i - 1) {
            go[stck.back().second].push_back(i);
        }
        stck.push_back(make_pair(f[i], i));
    }
    stck.clear();
    for (int i = n - 1; i >= 0; i -= 1) {
        while (!stck.empty() && stck.back().first < f[i]) {
            stck.pop_back();
        }
        if (!stck.empty() && stck.back().second != i + 1) {
            go[i].push_back(stck.back().second);
        }
        stck.push_back(make_pair(f[i], i));
    }
}

void build_gor_god() {
    gor.assign(n, vector<vector<int>>(m));
    for (int i = 0; i < n; i += 1) {
        vector<int> f(m);
        for (int j = 0; j < m; j += 1) {
            f[j] = a[i][j];
        }
        vector<vector<int>> go;
        build_go(f, go);
        for (int j = 0; j < m; j += 1) {
            gor[i][j] = go[j];
        }
    }
    god.assign(n, vector<vector<int>>(m));
    for (int j = 0; j < m; j += 1) {
        vector<int> f(n);
        for (int i = 0; i < n; i += 1) {
            f[i] = a[i][j];
        }
        vector<vector<int>> go;
        build_go(f, go);
        for (int i = 0; i < n; i += 1) {
            god[i][j] = go[i];
        }
    }
}

void build_dpths() {
    gor_dpth.assign(n, vector<vector<int>>(m));
    for (int j = 0; j < m; j += 1) {
        vector<int> lst_usd(m, n + 5);
        vector<int> lst_dpth(m, 0);
        for (int i = n - 1; i >= 0; i -= 1) {
            gor_dpth[i][j].resize(gor[i][j].size());
            for (int k = 0; k < (int)gor[i][j].size(); k += 1) {
                int x = gor[i][j][k];
                if (lst_usd[x] == i + 1) {
                    lst_dpth[x] += 1;
                } else {
                    lst_dpth[x] = 1;
                }
                lst_usd[x] = i;
                gor_dpth[i][j][k] = lst_dpth[x];
            }
        }
    }
    god_dpth.assign(n, vector<vector<int>>(m));
    for (int i = 0; i < n; i += 1) {
        vector<int> lst_usd(n, m + 5);
        vector<int> lst_dpth(n, 0);
        for (int j = m - 1; j >= 0; j -= 1) {
            god_dpth[i][j].resize(god[i][j].size());
            for (int k = 0; k < (int)god[i][j].size(); k += 1) {
                int x = god[i][j][k];
                if (lst_usd[x] == j + 1) {
                    lst_dpth[x] += 1;
                } else {
                    lst_dpth[x] = 1;
                }
                lst_usd[x] = j;
                god_dpth[i][j][k] = lst_dpth[x];
            }
        }
    }
}

ll solve_fuck() {
    build_gor_god();
    build_dpths();
    ll rs = 0;
    for (int i = 1; i < n - 1; i += 1) {
        for (int j = 1; j < m - 1; j += 1) {
            for (int x = 0; x < (int)gor[i][j - 1].size(); x += 1) {
                int j1 = gor[i][j - 1][x];
                int dpthx = gor_dpth[i][j - 1][x];
                for (int y = 0; y < (int)god[i - 1][j].size(); y += 1) {
                    int i1 = god[i - 1][j][y];
                    int dpthy = god_dpth[i - 1][j][y];
                    if ((j1 - j) <= dpthy && (i1 - i) <= dpthx) {
                        rs += 1;
                    }
                }
            }
        }
    }
    return rs;
}

ll solve_slow() {
    ll rs = 0;
    for (int i1 = 0; i1 < n; i1 += 1) {
        for (int i2 = i1 + 2; i2 < n; i2 += 1) {
            for (int j1 = 0; j1 < m; j1 += 1) {
                for (int j2 = j1 + 2; j2 < m; j2 += 1) {
                    int ok = true;
                    for (int i = i1 + 1; i < i2; i += 1) {
                        for (int j = j1 + 1; j < j2; j += 1) {
                            if (a[i][j] >= min(a[i1][j], a[i2][j]) || a[i][j] >= min(a[i][j1], a[i][j2])) {
                                ok = false;
                            }
                        }
                    }
                    rs += ok;
                }
            }
        }
    }
    return rs;
}

long long count_rectangles(vector<vector<int>> _a) {
    a = _a;
    n = (int)a.size();
    m = (int)a[0].size();
    if (n <= 2 || m <= 2) {
        return 0;
    }
    ll rs = solve_slow();
    return rs;
}