//  ↘ ⬇ ⬇ ⬇ ⬇ ⬇ ↙
//  ➡ @roadfromroi ⬅
//  ↗ ⬆ ⬆ ⬆ ⬆ ⬆ ↖
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#include "rect.h"
#define all(x) x.begin(), x.end()
using namespace std;
//#define LOCAL 1
struct segtree {
    int sz;
    vector<int> tree;
    void init(int n) {
        sz = 1;
        while (sz < n) {
            sz *= 2;
        }
        tree.assign(sz * 2, {});
    }
    int get(int l, int r) {
        l += sz;
        r += sz;
        int res = 0;
        while (l <= r) {
            if (l % 2) {
                res += tree[l];l++;
            }
            if (r % 2 == 0) {
                res += tree[r];
                r--;
            }
            l /= 2;r /= 2;
        }
        return res;
    }
    void ch(int v, int x) {
        v += sz;
        tree[v] += x;
        while (v != 1) {
            v /= 2;
            tree[v] = tree[v * 2] + tree[v * 2 + 1];
        }
    }
};
vector<array<int, 3>> retar(vector<int> & a, int tosrt = 1) {
    int n = a.size();
    vector<int> nxtmore(n), prvmore(n);
    for (int i = 0; i < n; ++i) {
        prvmore[i] = i-1;
        while (prvmore[i] != -1 and a[i] > a[prvmore[i]])
            prvmore[i] = prvmore[prvmore[i]];
    }
    for (int i = n - 1; i >= 0; --i) {
        nxtmore[i] = i+1;
        while (nxtmore[i] != n and a[i] > a[nxtmore[i]])
            nxtmore[i] = nxtmore[nxtmore[i]];
    }
    vector<array<int, 3>> segs;
    for (int i = 0; i < n; ++i) {
        if (nxtmore[i] < n and i+2 <= nxtmore[i]) {
            segs.push_back({i+1, nxtmore[i] - 1, 1});
        }
        if (prvmore[i] > -1 and prvmore[i] + 1 <= i - 1 and a[prvmore[i]] > a[i]) {
            segs.push_back({prvmore[i] + 1, i - 1, 1});
        }
    }
    if (tosrt)
        sort(all(segs));
    return segs;
}
void updlst(vector<array<int, 3>> &a, vector<array<int, 3>> &b, vector<array<int, 3>> &toaddkaa) {
    int v1 = 0;
    for (auto &i : b) {
        while (v1 != a.size() and make_pair(a[v1][0], a[v1][1]) < make_pair(i[0], i[1])) {
            toaddkaa.push_back(a[v1]);
            v1++;
        }
        if (v1 != a.size() and make_pair(a[v1][0], a[v1][1]) == make_pair(i[0], i[1])) {
            i[2] = a[v1][2] + 1;
            v1++;
        }
    }
    while (v1 != a.size()) {
        toaddkaa.push_back(a[v1]);
        v1++;
    }
}
long long count_rectangles(std::vector<std::vector<int> > a) {
    vector<vector<array<int, 3>>> bebas(a.size());
    vector<vector<array<int, 3>>> zpr2(a[0].size());
    for (int i = 1; i < a.size(); ++i) {
        bebas[i] = retar(a[i]);
        if (i + 1 == a.size())
            bebas[i] = {};
        vector<array<int, 3>> losed;
        updlst(bebas[i-1], bebas[i], losed);
        for (auto [l1, r1, glb] : bebas[i]) {
            int r2 = i;
            int l2 = i;
            zpr2[r1].push_back({l2, r2, r1-l1+1});
            //cout << "D " << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;
        }
        for (auto [l1, r1, glb] : losed) {
            int r2 = i - 1;
            int l2 = i - glb;
            zpr2[r1].push_back({l2, r2, r1-l1+1});
            //cout << l1 << ' ' << r1 << ' ' << l2 << ' ' << r2 << endl;
        }
    }
    vector<vector<int>> a2(a[0].size(), vector<int>(a.size()));
    for (int i = 0; i < a.size(); ++i) {
        for (int j = 0; j < a[i].size(); ++j) {
            a2[j][i] = a[i][j];
        }
    }
    for (int i = 0; i < a2.size(); ++i) {
        for (int j = 0; j < a2[i].size(); ++j) {
            //cout << a2[i][j] << ' ';
        }
        //cout << '\n';
    }
    long long reska = 0;
    vector<vector<array<int, 3>>> bebas2(a2.size());
    for (int i = 1; i + 1 < a2.size(); ++i) {
        bebas2[i] = retar(a2[i]);
        vector<array<int, 3>> losed;
        updlst(bebas2[i-1], bebas2[i], losed);
        for (auto teba : bebas2[i]) {
            int mglb = 0;
            for (auto jeba : zpr2[i]) {
                if (teba[2] >= jeba[2] and jeba[0] <= teba[0] and teba[1] <= jeba[1]) {
                    mglb = max(mglb, jeba[2]);
                    //cout  << i << ' ' << teba[0] << ' ' << teba[1] << ' ' << jeba[0] << ' ' << jeba[1] << endl;
                }
            }
            reska += mglb;
        }
    }
    return reska;
}

#ifdef LOCAL

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++)	{
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }

    long long result = count_rectangles(a);
    cout << result << '\n';
    return 0;
}

#endif