Problem: One fine day Sasha went to the park for a walk. In the park, he saw that his favorite bench is occupied, and he had to sit down on the neighboring one. He sat down and began to listen to the silence. Suddenly, he got a question: what if in different parts of the park, the silence sounds in different ways? So it was. Let's divide the park into 1 × 1 meter squares and call them cells, and numerate rows from 1 to n from up to down, and columns from 1 to m from left to right. And now, every cell can be described with a pair of two integers (x, y), where x — the number of the row, and y — the number of the column. Sasha knows that the level of silence in the cell (i, j) equals to f_{i,j}, and all f_{i,j} form a permutation of numbers from 1 to n ⋅ m. Sasha decided to count, how many are there pleasant segments of silence?

Let's take some segment [l … r]. Denote S as the set of cells (i, j) that l ≤ f_{i,j} ≤ r. Then, the segment of silence [l … r] is pleasant if there is only one simple path between every pair of cells from S (path can't contain cells, which are not in S). In other words, set S should look like a tree on a plain. Sasha has done this task pretty quickly, and called the algorithm — "algorithm of silence's sounds".

Time passed, and the only thing left from the algorithm is a legend. To prove the truthfulness of this story, you have to help Sasha and to find the number of different pleasant segments of silence. Two segments [l_1 … r_1], [l_2 … r_2] are different, if l_1 ≠ l_2 or r_1 ≠ r_2 or both at the same time.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 1000, 1 ≤ n ⋅ m ≤ 2 ⋅ 10^5) — the size of the park.

Each from next n lines contains m integers f_{i,j} (1 ≤ f_{i,j} ≤ n ⋅ m) — the level of silence in the cell with number (i, j).

It is guaranteed, that all f_{i,j} are different.

Output

Print one integer — the number of pleasant segments of silence.

Examples

Input

1 5
1 2 3 4 5


Output

15

Input

2 3
1 2 3
4 5 6


Output

15

Input

4 4
4 3 2 16
1 13 14 15
5 7 8 12
6 11 9 10


Output

50

Note

In the first example, all segments of silence are pleasant.

In the second example, pleasant segments of silence are the following:

<image>

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
namespace CPTH {
template <typename valueType, typename modType>
struct SegmentTreeNode {
  size_t id;
  long long left, right;
  valueType val;
  modType mod;
};
template <typename valueType, typename modType,
          bool elementModificationOnly = false>
class SegmentTree {
 public:
  SegmentTree() = default;
  SegmentTree(
      const std::vector<valueType> &_initValue,
      std::function<valueType(const valueType &, const valueType &)> _merge,
      std::function<void(SegmentTreeNode<valueType, modType> &,
                         const modType &)>
          _update,
      long long _startPoint = 1, const valueType &_valueZero = valueType(),
      const modType &_modZero = modType());
  void init(
      const std::vector<valueType> &_initValue,
      std::function<valueType(const valueType &, const valueType &)> _merge,
      std::function<void(SegmentTreeNode<valueType, modType> &,
                         const modType &)>
          _update,
      long long _startPoint = 1, const valueType &_valueZero = valueType(),
      const modType &_modZero = modType());
  void modify(long long l, long long r, const modType &mod);
  void modify(long long p, const modType &mod);
  valueType query(long long l, long long r);
  valueType query(long long p);

 private:
  void pushup(size_t cur);
  void pushdown(size_t cur);
  void build(size_t cur, long long l, long long r,
             const std::vector<valueType> &initValue);
  void m_init(
      const std::vector<valueType> &_initValue,
      std::function<valueType(const valueType &, const valueType &)> _merge,
      std::function<void(SegmentTreeNode<valueType, modType> &,
                         const modType &)>
          _update,
      const valueType &_valueZero, const modType &_modZero);
  void modify(size_t cur, long long l, long long r, long long L, long long R,
              const modType &mod);
  valueType query(size_t cur, long long l, long long r, long long L,
                  long long R);
  std::function<valueType(const valueType &, const valueType &)> merge;
  std::function<void(SegmentTreeNode<valueType, modType> &, const modType &)>
      update;
  std::vector<SegmentTreeNode<valueType, modType>> nodes;
  long long leftRange = 0, rightRange = 0;
  valueType valueZero;
  modType modZero;
};
template <typename valueType, typename modType, bool elementModificationOnly>
SegmentTree<valueType, modType, elementModificationOnly>::SegmentTree(
    const std::vector<valueType> &_initValue,
    std::function<valueType(const valueType &, const valueType &)> _merge,
    std::function<void(SegmentTreeNode<valueType, modType> &, const modType &)>
        _update,
    long long _startPoint, const valueType &_valueZero,
    const modType &_modZero) {
  init(_initValue, _merge, _update, _startPoint, _valueZero, _modZero);
}
template <typename valueType, typename modType, bool elementModificationOnly>
void SegmentTree<valueType, modType, elementModificationOnly>::init(
    const std::vector<valueType> &_initValue,
    std::function<valueType(const valueType &, const valueType &)> _merge,
    std::function<void(SegmentTreeNode<valueType, modType> &, const modType &)>
        _update,
    long long _startPoint, const valueType &_valueZero,
    const modType &_modZero) {
  assert(_startPoint >= LLONG_MIN / 2);
  assert(_startPoint <= LLONG_MAX / 2 - (long long)_initValue.size());
  leftRange = _startPoint;
  rightRange = _startPoint + _initValue.size();
  m_init(_initValue, _merge, _update, _valueZero, _modZero);
}
template <typename valueType, typename modType, bool elementModificationOnly>
void SegmentTree<valueType, modType, elementModificationOnly>::modify(
    long long l, long long r, const modType &mod) {
  assert(!elementModificationOnly);
  modify(1, leftRange, rightRange, l, r, mod);
}
template <typename valueType, typename modType, bool elementModificationOnly>
void SegmentTree<valueType, modType, elementModificationOnly>::modify(
    long long p, const modType &mod) {
  assert(p < LLONG_MAX);
  modify(1, leftRange, rightRange, p, p + 1, mod);
}
template <typename valueType, typename modType, bool elementModificationOnly>
valueType SegmentTree<valueType, modType, elementModificationOnly>::query(
    long long l, long long r) {
  return query(1, leftRange, rightRange, l, r);
}
template <typename valueType, typename modType, bool elementModificationOnly>
valueType SegmentTree<valueType, modType, elementModificationOnly>::query(
    long long p) {
  return query(p, p + 1);
}
template <typename valueType, typename modType, bool elementModificationOnly>
void SegmentTree<valueType, modType, elementModificationOnly>::pushup(
    size_t cur) {
  nodes[cur].val = merge(nodes[cur << 1].val, nodes[cur << 1 | 1].val);
}
template <typename valueType, typename modType, bool elementModificationOnly>
void SegmentTree<valueType, modType, elementModificationOnly>::pushdown(
    size_t cur) {
  update(nodes[cur << 1], nodes[cur].mod);
  update(nodes[cur << 1 | 1], nodes[cur].mod);
  nodes[cur].mod = modZero;
}
template <typename valueType, typename modType, bool elementModificationOnly>
void SegmentTree<valueType, modType, elementModificationOnly>::build(
    size_t cur, long long l, long long r,
    const std::vector<valueType> &initValue) {
  nodes[cur].id = cur;
  nodes[cur].left = l;
  nodes[cur].right = r;
  nodes[cur].mod = modZero;
  if (l == r - 1)
    nodes[cur].val = initValue[l - leftRange];
  else {
    build(cur << 1, l, (l + r) >> 1, initValue);
    build(cur << 1 | 1, (l + r) >> 1, r, initValue);
    pushup(cur);
  }
}
template <typename valueType, typename modType, bool elementModificationOnly>
void SegmentTree<valueType, modType, elementModificationOnly>::m_init(
    const std::vector<valueType> &_initValue,
    std::function<valueType(const valueType &, const valueType &)> _merge,
    std::function<void(SegmentTreeNode<valueType, modType> &, const modType &)>
        _update,
    const valueType &_valueZero, const modType &_modZero) {
  merge = _merge;
  update = _update;
  valueZero = _valueZero;
  modZero = _modZero;
  nodes.resize((rightRange - leftRange) << 2);
  build(1, leftRange, rightRange, _initValue);
}
template <typename valueType, typename modType, bool elementModificationOnly>
void SegmentTree<valueType, modType, elementModificationOnly>::modify(
    size_t cur, long long l, long long r, long long L, long long R,
    const modType &mod) {
  if (l >= R || r <= L) return;
  if (L <= l && r <= R)
    update(nodes[cur], mod);
  else {
    if (!elementModificationOnly) pushdown(cur);
    modify(cur << 1, l, (l + r) >> 1, L, R, mod);
    modify(cur << 1 | 1, (l + r) >> 1, r, L, R, mod);
    pushup(cur);
  }
}
template <typename valueType, typename modType, bool elementModificationOnly>
valueType SegmentTree<valueType, modType, elementModificationOnly>::query(
    size_t cur, long long l, long long r, long long L, long long R) {
  if (l >= R || r <= L) return valueZero;
  if (L <= l && r <= R) return nodes[cur].val;
  if (!elementModificationOnly) pushdown(cur);
  return merge(query(cur << 1, l, (l + r) >> 1, L, R),
               query(cur << 1 | 1, (l + r) >> 1, r, L, R));
}
}  // namespace CPTH
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;
const double inf = 1e121;
const double eps = 1e-10;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randint(int l, int r) {
  int out = rng() % (r - l + 1) + l;
  return out >= l ? out : out + r - l + 1;
}
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
template <typename A, typename B, typename C, typename D, typename E>
string to_string(tuple<A, B, C, D, E> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + "," +
         to_string(get<4>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
template <typename T>
struct is_pair {
  static const bool value = false;
};
template <typename T, typename U>
struct is_pair<std::pair<T, U>> {
  static const bool value = true;
};
const int INF = 0x3f3f3f3f;
template <typename T>
typename enable_if<!is_integral<T>::value && !is_pair<T>::value, void>::type
read(T &x) {
  cin >> x;
}
long long read() {
  char c;
  long long out = 0, f = 1;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar()) {
  }
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) out = (out << 3) + (out << 1) + c - '0';
  return out * f;
}
template <typename T>
typename enable_if<is_integral<T>::value, T>::type read(T &x) {
  char c;
  T f = 1;
  x = 0;
  for (c = getchar(); !isdigit(c) && c != '-'; c = getchar()) {
  }
  if (c == '-') {
    f = -1;
    c = getchar();
  }
  for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0';
  return x *= f;
}
char read(char &x) {
  for (x = getchar(); isspace(x); x = getchar()) {
  }
  return x;
}
double read(double &x) {
  scanf("%lf", &x);
  return x;
}
template <typename T>
typename enable_if<!is_integral<T>::value && !is_pair<T>::value, void>::type
write(const T &x) {
  cout << x;
}
template <typename T>
typename enable_if<is_integral<T>::value, void>::type write(const T &x) {
  if (x < 0) {
    putchar('-');
    write(-x);
    return;
  }
  if (x > 9) write(x / 10);
  putchar(x % 10 + '0');
}
void write(char x) { putchar(x); }
void write(double x) { printf("%.12lf", x); }
void write(long double x) { cout << fixed << setprecision(12) << x; }
template <typename T>
typename enable_if<is_pair<T>::value, void>::type read(T &x) {
  read(x.first);
  read(x.second);
}
template <typename T>
typename enable_if<is_pair<T>::value, void>::type write(const T &x) {
  write(x.first);
  putchar(' ');
  write(x.second);
}
template <typename T, typename... Args>
void read(T &x, Args &...args) {
  read(x);
  read(args...);
}
template <
    typename OutputIt,
    typename = typename enable_if<
        is_same<output_iterator_tag,
                typename iterator_traits<OutputIt>::iterator_category>::value ||
        (is_base_of<forward_iterator_tag, typename iterator_traits<OutputIt>::
                                              iterator_category>::value &&
         !is_const<OutputIt>::value)>::type>
void read(OutputIt __first, OutputIt __last) {
  for (; __first != __last; ++__first) read(*__first);
}
template <
    typename InputIt,
    typename = typename enable_if<is_base_of<
        input_iterator_tag,
        typename iterator_traits<InputIt>::iterator_category>::value>::type>
void wts(InputIt __first, InputIt __last) {
  bool isFirst = true;
  for (; __first != __last; ++__first) {
    if (isFirst)
      isFirst = false;
    else
      putchar(' ');
    write(*__first);
  }
  putchar('\n');
}
template <
    typename InputIt,
    typename = typename enable_if<is_base_of<
        input_iterator_tag,
        typename iterator_traits<InputIt>::iterator_category>::value>::type>
void wtb(InputIt __first, InputIt __last) {
  for (; __first != __last; ++__first) {
    write(*__first);
    putchar('\n');
  }
}
template <typename T>
void wts(const T &x) {
  write(x);
  putchar(' ');
}
template <typename T>
void wtb(const T &x) {
  write(x);
  putchar('\n');
}
template <typename T>
void wte(const T &x) {
  write(x);
  exit(0);
}
template <typename T, typename... Args>
void wts(const T &x, Args... args) {
  wts(x);
  wts(args...);
}
template <typename T, typename... Args>
void wtb(const T &x, Args... args) {
  wts(x);
  wtb(args...);
}
template <typename T, typename... Args>
void wte(const T &x, Args... args) {
  wts(x);
  wte(args...);
}
template <typename T1, typename T2>
inline bool up(T1 &x, const T2 &y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T1, typename T2>
inline bool dn(T1 &x, const T2 &y) {
  return y < x ? x = y, 1 : 0;
}
template <typename T1, typename T2, typename T3>
inline bool inRange(const T1 &x, const T2 &l, const T3 &r) {
  return !(x < l) && !(r < x);
}
template <typename T1, typename T2>
inline auto minOfDifferentTypes(const T1 &x, const T2 &y)
    -> decltype(x < y ? x : y) {
  return x < y ? x : y;
}
template <typename T1, typename T2>
inline auto maxOfDifferentTypes(const T1 &x, const T2 &y)
    -> decltype(x < y ? y : x) {
  return x < y ? y : x;
}
template <typename T1, typename T2, typename T3>
inline T1 &madd(T1 &x, const T2 &y, const T3 &modulo) {
  return x = (long long)(x + y + modulo) % modulo;
}
template <typename T1, typename T2, typename T3>
inline T1 &mmul(T1 &x, const T2 &y, const T3 &modulo) {
  return x = (long long)x * y % modulo;
}
inline int modadd(int x, int y, int modulo) {
  return x + y >= modulo ? x + y - modulo : x + y;
}
inline int isinf(int x) { return x < INF ? x : -1; }
inline void yesno(bool x) { wtb(x ? "Yes" : "No"); }
using namespace CPTH;
struct LCT {
  struct Node {
    int pa;
    vector<int> ch;
    bool rev;
    Node() : pa(0), ch(2), rev(false) {}
  };
  vector<Node> t;
  LCT(int n) : t(n + 1) {}
  bool notRoot(int x) { return x == t[t[x].pa].ch[0] || x == t[t[x].pa].ch[1]; }
  void rotate(int x) {
    int y = t[x].pa;
    int z = t[y].pa;
    int k = x == t[y].ch[1];
    if (notRoot(y)) t[z].ch[y == t[z].ch[1]] = x;
    t[x].pa = z;
    t[y].ch[k] = t[x].ch[k ^ 1];
    t[t[x].ch[k ^ 1]].pa = y;
    t[x].ch[k ^ 1] = y;
    t[y].pa = x;
  }
  void reverse(int x) {
    swap(t[x].ch[0], t[x].ch[1]);
    t[x].rev ^= 1;
  }
  void pushdown(int x) {
    if (t[x].rev) {
      reverse(t[x].ch[0]);
      reverse(t[x].ch[1]);
      t[x].rev = false;
    }
  }
  void splay(int x) {
    static stack<int> stk;
    stk.push(x);
    for (int u = x; notRoot(u); u = t[u].pa) stk.push(t[u].pa);
    while (!stk.empty()) {
      pushdown(stk.top());
      stk.pop();
    }
    while (notRoot(x)) {
      int y = t[x].pa;
      int z = t[y].pa;
      if (notRoot(y)) rotate((x == t[y].ch[1]) ^ (y == t[z].ch[1]) ? x : y);
      rotate(x);
    }
  }
  void splay(int x, int goal) {
    while (t[x].pa != goal) {
      int y = t[x].pa;
      int z = t[y].pa;
      if (z != goal) rotate((x == t[y].ch[1]) ^ (y == t[z].ch[1]) ? x : y);
      rotate(x);
    }
  }
  void access(int x) {
    for (int y = 0; x; x = t[y = x].pa) {
      splay(x);
      t[x].ch[1] = y;
    }
  }
  void makeRoot(int x) {
    access(x);
    splay(x);
    reverse(x);
  }
  int findRoot(int x) {
    access(x);
    splay(x);
    while (t[x].ch[0]) {
      pushdown(x);
      x = t[x].ch[0];
    }
    splay(x);
    return x;
  }
  bool link(int x, int y) {
    makeRoot(x);
    if (findRoot(y) == x) return false;
    access(y);
    splay(y);
    t[x].pa = y;
    return true;
  }
  void cut(int x, int y) {
    makeRoot(x);
    access(y);
    t[x].ch[1] = t[y].pa = 0;
  }
};
signed main() {
  int n, m;
  read(n, m);
  vector<vector<int>> a(n, vector<int>(m + 1));
  for (auto &x : a) read(((x).begin() + 1), (x).end());
  LCT lct(n * m);
  int r = 0;
  vector<vector<int>> g(n * m + 1);
  vector<pair<int, int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
  for (int i = (0), iend = (n - 1); i <= iend; ++i) {
    for (int j = (1), jend = (m); j <= jend; ++j) {
      for (int k = (0), kend = (3); k <= kend; ++k) {
        int ni = i + dir[k].first;
        int nj = j + dir[k].second;
        if (inRange(ni, 0, n - 1) && inRange(nj, 1, m))
          g[a[i][j]].push_back(a[ni][nj]);
      }
    }
  }
  vector<int> mxr(n * m + 1);
  for (int l = (1), lend = (n * m); l <= lend; ++l) {
    bool flag = true;
    while (flag && r < n * m) {
      ++r;
      for (int i = (0), iend = ((int)g[r].size() - 1); i <= iend; ++i) {
        int v = g[r][i];
        if (inRange(v, l, r - 1)) {
          if (!lct.link(r, v)) {
            for (int j = (0), jend = (i - 1); j <= jend; ++j) {
              int w = g[r][j];
              if (inRange(w, l, r - 1)) lct.cut(r, w);
            }
            --r;
            flag = false;
            break;
          }
        }
      }
    }
    mxr[l] = r;
    for (auto v : g[l]) {
      if (inRange(v, l + 1, r)) {
        lct.cut(l, v);
      }
    }
  }
  SegmentTree<pair<int, int>, int> seg(
      vector<pair<int, int>>(n * m, pair<int, int>(0, 1)),
      [](pair<int, int> x, pair<int, int> y) {
        if (x.first == y.first)
          return pair<int, int>(x.first, x.second + y.second);
        return minOfDifferentTypes(x, y);
      },
      [](SegmentTreeNode<pair<int, int>, int> &u, int x) {
        u.val.first += x;
        u.mod += x;
      },
      1, pair<int, int>(INF, 0));
  long long ans = 0;
  for (int l = (n * m), lend = (1); l >= lend; --l) {
    seg.modify(l, n * m + 1, 1);
    for (auto v : g[l]) {
      if (inRange(v, l + 1, mxr[l])) {
        seg.modify(v, n * m + 1, -1);
      }
    }
    pair<int, int> res = seg.query(l, mxr[l] + 1);
    if (res.first == 1) ans += res.second;
  }
  wtb(ans);
  return 0;
}