#include <bits/stdc++.h>

#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

array dxs{-1L, 1L, 0L, 0L};
array dys{0L, 0L, -1L, 1L};

int main() {
    int64_t n;
    cin >> n;

    vector p(n * n + 1, 0L), rev(n * n + 1, 0L);
    for (auto i : irange(1L, n * n + 1)) {
        cin >> p[i];
        rev[p[i]] = i;
    }

    // dijkstra
    vector mm(n * n + 1, n * n + 1);
    vector parents(n * n + 1, 0L);
    {
        using V = pair<int64_t, int64_t>;
        priority_queue<V, vector<V>, std::greater<>> q;

        for (auto i : irange(1L, n * n + 1)) {
            if (i % n == 0 || i % n == n - 1 || i / n == 0 || i / n == n - 1) {
                mm[i] = i;
                q.emplace(i, i);
            }
        }

        while (!q.empty()) {
            auto [cost, idx] = q.top();
            q.pop();

            if (cost < mm[idx]) {
                continue;
            }

            auto r = idx / n;
            auto c = idx % n;

            for (auto i : irange(0L, 4L)) {
                auto nr = r + dys[i];
                auto nc = c + dxs[i];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                    continue;
                }

                auto next = nr * n + nc;
                auto next_cost = max(cost, rev[next]);
                if (next_cost < mm[next]) {
                    mm[next] = next_cost;
                    parents[next] = idx;
                    q.emplace(next_cost, next);
                }
            }
        }
    }

    int64_t ans = 0;
    vector costs(n * n + 1, 0L);
    vector<bool> selected(n * n + 1, false);
    for (auto pp : p | reversed) {
        ans += costs[pp];

        queue<int64_t> q;
        q.push(pp);
        ++costs[pp];
        selected[pp] = true;

        while (!q.empty()) {
            auto idx = q.front();
            q.pop();

            auto r = idx / n;
            auto c = idx % n;

            for (auto i : irange(0L, 4L)) {
                auto nr = r + dys[i];
                auto nc = c + dxs[i];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) {
                    continue;
                }

                auto next = nr * n + nc;

                if (parents[next] != idx) {
                    continue;
                }

                pair<int64_t, int64_t> m{n * n + 1, n * n + 1};
                for (auto j : irange(0L, 4L)) {
                    auto nr2 = nr + dys[j];
                    auto nc2 = nc + dxs[j];
                    if (nr2 < 0 || nr2 >= n || nc2 < 0 || nc2 >= n) {
                        continue;
                    }

                    auto next2 = nr2 * n + nc2;
                    m = min(m, make_pair(costs[next2], mm[next2]));
                }

                costs[next] = m.first + (selected[next] ? 1 : 0);
                mm[next] = max(m.second, next);

                q.push(next);
            }
        }
    }

    cout << ans << endl;
}