Problem: There are three arrays a, b and c. Each of them consists of n integers. SmallY wants to find three integers u, v, w (0 ≤ u, v, w ≤ n) such that the following condition holds: each number that appears in the union of a, b and c, appears either in the first u elements of a, or in the first v elements of b, or in the first w elements of c. Of course, SmallY doesn't want to have huge numbers u, v and w, so she wants sum u + v + w to be as small as possible.

Please, help her to find the minimal possible sum of u + v + w.

Input

The first line contains a single integer n (1 ≤ n ≤ 105). The second line contains n space-separated integers a1, a2, ..., an — array a. The third line contains the description of array b in the same format. The fourth line contains the description of array c in the same format. The following constraint holds: 1 ≤ ai, bi, ci ≤ 109.

Output

Print a single integer — the minimum possible sum of u + v + w.

Examples

Input

3
1 1 101
1 2 1
3 2 1


Output

5

Input

5
1 1 2 2 3
2 2 4 3 3
3 3 1 1 1


Output

5

Note

In the first example you should choose u = 3, v = 0, w = 2. 

In the second example you should choose u = 1, v = 3, w = 1.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int nmax = 1e5 + 42;
struct info {
  int u, v, w;
};
info interesting[nmax * 3];
int id;
void add(info current) {
  id++;
  interesting[id] = current;
}
int n;
int a[nmax], b[nmax], c[nmax];
map<int, int> seena, seenb, seenc;
bool cmp(info a, info b) { return a.u < b.u; }
set<pair<int, int> > active;
set<pair<int, int> > least;
void update(int v, int w) {
  pair<int, int> now = {v, w};
  set<pair<int, int> >::iterator it;
  it = active.lower_bound(now);
  if ((*it).second >= w) return;
  while (1) {
    it = active.lower_bound(now);
    pair<int, int> lower = *it;
    it--;
    pair<int, int> lower_before = *it;
    it--;
    pair<int, int> lower_before_before = *it;
    if (lower_before.second <= w) {
      active.erase(lower_before);
      least.erase({lower_before.first + lower.second, lower.second});
      least.erase({lower_before_before.first + lower_before.second,
                   lower_before.second});
      least.insert({lower_before_before.first + lower.second, lower.second});
    } else
      break;
  }
  it = active.lower_bound(now);
  pair<int, int> lower = *it;
  it--;
  pair<int, int> lower_before = *it;
  least.erase({lower_before.first + lower.second, lower.second});
  least.insert({lower_before.first + now.second, now.second});
  least.insert({now.first + lower.second, lower.second});
  active.insert(now);
}
int query() {
  int ret = 3 * n, prev = 1e9;
  for (auto k : active) {
    ret = min(ret, k.second + prev);
    prev = k.first;
  }
  return ret;
}
int main() {
  scanf("%i", &n);
  for (int i = 1; i <= n; i++) scanf("%i", &a[i]);
  for (int i = n; i >= 1; i--) seena[a[i]] = i;
  for (int i = 1; i <= n; i++) scanf("%i", &b[i]);
  for (int i = n; i >= 1; i--) seenb[b[i]] = i;
  for (int i = 1; i <= n; i++) scanf("%i", &c[i]);
  for (int i = n; i >= 1; i--) seenc[c[i]] = i;
  for (int i = 1; i <= n; i++) {
    info current;
    current.u = 3 * n + 1;
    if (seena.count(a[i])) current.u = seena[a[i]];
    current.v = 3 * n + 1;
    if (seenb.count(a[i])) current.v = seenb[a[i]];
    current.w = 3 * n + 1;
    if (seenc.count(a[i])) current.w = seenc[a[i]];
    if (current.u == i) add(current);
  }
  for (int i = 1; i <= n; i++) {
    info current;
    current.u = 3 * n + 1;
    if (seena.count(b[i])) current.u = seena[b[i]];
    current.v = 3 * n + 1;
    if (seenb.count(b[i])) current.v = seenb[b[i]];
    current.w = 3 * n + 1;
    if (seenc.count(b[i])) current.w = seenc[b[i]];
    if (current.u > n && current.v == i) add(current);
  }
  for (int i = 1; i <= n; i++) {
    info current;
    current.u = 3 * n + 1;
    if (seena.count(c[i])) current.u = seena[c[i]];
    current.v = 3 * n + 1;
    if (seenb.count(c[i])) current.v = seenb[c[i]];
    current.w = 3 * n + 1;
    if (seenc.count(c[i])) current.w = seenc[c[i]];
    if (current.u > n && current.v > n && current.w == i) add(current);
  }
  active.insert({0, 3 * n + 2});
  active.insert({3 * n + 2, 0});
  least.insert({0, 0});
  sort(interesting + 1, interesting + id + 1, cmp);
  for (int i = 2; i <= id; i++)
    assert(interesting[i - 1].u != interesting[i].u ||
           interesting[i - 1].v != interesting[i].v ||
           interesting[i - 1].w != interesting[i].w);
  int ret = 3 * n;
  for (int u = n; u >= 0; u--) {
    bool stop = 0;
    while (id && u < interesting[id].u) {
      if (interesting[id].v > n && interesting[id].w > n) {
        stop = 1;
        break;
      }
      update(interesting[id].v, interesting[id].w);
      id--;
    }
    if (stop) break;
    int q = (*least.begin()).first;
    ret = min(ret, u + q);
  }
  printf("%i\n", ret);
  return 0;
}