#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std;

#define f first
#define s second
#define pb push_back
#define pii pair<int, int>
#define vi vector<int>
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)((v).size())
#define f0(a) memset(a, 0, sizeof(a))
#define ll long long
struct Point {
  void read() {
    cin >> x >> y >> z;
  }

  int dist(const Point &o) const {
    return abs(x - o.x) + abs(y - o.y) + max(0, o.z - z);
  }

  int x = 0, y = 0, z = 0;
};
int dist[18][1<<18];

int main() {
  int n;
  cin >> n;
  vector<Point> points(n);
  for (int i = 0; i < n; ++i) {
    points[i].read();
  }

  using state = tuple<int, int, int>;
  priority_queue<state, vector<state>, greater<state>> pq;
  for (int i = 0; i < n; ++i) {
    fill(dist[i], dist[i] + (1 << 18), (int)1e9); 
  }
  dist[0][1] = 0;
  pq.emplace(0, 0, 1);

  while (!pq.empty()) {
    auto [cost, v, mask] = pq.top();
    pq.pop();
    if (dist[v][mask] != cost) continue;

    for (int u = 0; u < n; ++u) {
      int w = points[v].dist(points[u]);
      int nmask = (mask | (1 << u));
      if (dist[u][nmask] > dist[v][mask] + w) {
        dist[u][nmask] = dist[v][mask] + w;
        pq.emplace(dist[u][nmask], u, nmask);
      }
    }
  }
  int ans = dist[0][(1 << n) - 1];
  for (int u = 0; u < n; ++u) {
    ans = min(ans, dist[u][(1 << n) - 1] + points[u].dist(points[0]));
  }
  cout << ans << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define loop(i, a, n) for (int i = a; i < n; i++)
#define loope(i, b, n) for (int i = b; i <= n; i++)
#define loopit(a) for (auto it = a.begin(); it != a.end(); it++)
#define ms(a, b) memset(a, b, sizeof(a))
#define pb(a) push_back(a)
#define MP make_pair
#define pi pair<int, int>
#define ff first
#define ss second
#define bloop(i, a, b) for (int i = a; i > b; i--)
#define bloope(i, a, b) for (int i = a; i >= b; i--)
#define PQ priority_queue<int> pq;
#define vi vector<int>
#define vii vector<vector<int>>
#define si set<int>
#define NO cout<<"NO\n";
#define YES cout<<"YES\n";
#define MPQ priority_queue<pi, vector<int>, greater<pi>> mpq;
#define io                        \
    ios_base::sync_with_stdio(0); \
    cin.tie(NULL);                \
// #include < ext / pb_ds / assoc_container.hpp >
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less<int>, rb_tree_tag,
//         tree_order_statistics_node_update>
//         ordered_set;
ll ceil(ll a, ll b) {
    return (a + b - 1) / b;
}
//graph theory
vector<vi> adj;
vi vis;

int dfs(int cur) {
    int ret = 1;
    vis[cur] = 1;
    // cout << cur << ",";
    for (const auto &v : adj[cur]) {
        if (vis[v])continue;
        ret += dfs(v);
    }
    return ret;
}
const int maxm = 2 * 1e5 + 1;

void solve()
{
    int n; cin >> n;
    vi a(n);
    loop(i, 0, n)cin >> a[i];
    adj = vector<vi>(maxm + 1);
    vis = vi(maxm + 1);

    int ans = 0;
    loop(i, 0, n / 2) {
        if (a[i] == a[n - i - 1])continue;
        adj[a[i]].pb(a[n - i - 1]);
        adj[a[n - i - 1]].pb(a[i]);
    }

    loop(i, 0, n) {
        if (vis[a[i]])continue;
        ans += dfs(a[i]) - 1;
        // cout << "\n";
        // cout << a[i] << " " << ans << "\n";
    }
    cout << ans << "\n";
}
int main()
{
    io;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int test = 1, i = 0;
    // cin >> test;
    while (i++ != test)
    {
        // cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}
