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;
int n, a[4][100100], tot, cnt;
const int Maxn = 1 << 30;
struct Node {
  int v, id, from;
} seq[1001000];
struct NNode {
  int v[4];
  void init() { v[1] = v[2] = v[3] = 3 * n; }
} whe[1001000];
struct NNNode {
  int x, y;
};
set<NNNode> F;
multiset<int> sum;
bool operator<(NNNode x, NNNode y) {
  return x.x < y.x || (x.x == y.x && x.y < y.y);
}
bool cmp1(Node x, Node y) { return x.v < y.v; }
bool cmp(NNode x, NNode y) { return x.v[1] > y.v[1]; }
void insert(int x) {
  set<NNNode>::iterator s1, s2, s3;
  NNNode inwho = (NNNode){whe[x].v[2], whe[x].v[3]};
  F.insert(inwho);
  s1 = F.find(inwho);
  s3 = s1;
  s3++;
  if ((*s3).x >= (*s1).x && (*s3).y >= (*s1).y) {
    F.erase(inwho);
    return;
  }
  s2 = s1;
  s2--;
  s3 = s1;
  s3++;
  if (sum.find((*s3).y + (*s2).x) != sum.end())
    sum.erase(sum.find((*s3).y + (*s2).x));
  while (true) {
    s1 = F.find(inwho);
    s2 = s1;
    s2--;
    if (!((*s2).x <= (*s1).x && (*s2).y <= (*s1).y)) break;
    s3 = s2;
    s3--;
    if (sum.find((*s2).y + (*s3).x) != sum.end())
      sum.erase(sum.find((*s2).y + (*s3).x));
    F.erase(s2);
  }
  s1 = F.find(inwho);
  s3 = s1;
  s3++;
  sum.insert((*s1).x + (*s3).y);
  s2 = s1;
  s2--;
  sum.insert((*s2).x + (*s1).y);
}
void work() {
  sort(whe + 1, whe + cnt + 1, cmp);
  F.insert((NNNode){3 * n + 2, 0});
  F.insert((NNNode){0, 3 * n + 2});
  sum.insert(0);
  int l = 1, ans = Maxn;
  for (int u = n; u >= 0; u--) {
    while (whe[l].v[1] > u) insert(l), l++;
    ans = min(ans, u + (*sum.begin()));
  }
  printf("%d\n", ans);
}
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++)
    scanf("%d", &a[1][i]), seq[++tot] = (Node){a[1][i], i, 1};
  for (int i = 1; i <= n; i++)
    scanf("%d", &a[2][i]), seq[++tot] = (Node){a[2][i], i, 2};
  for (int i = 1; i <= n; i++)
    scanf("%d", &a[3][i]), seq[++tot] = (Node){a[3][i], i, 3};
  sort(seq + 1, seq + tot + 1, cmp1);
  a[seq[1].from][seq[1].id] = 1;
  cnt++;
  whe[1].init();
  whe[cnt].v[seq[1].from] = min(whe[cnt].v[seq[1].from], seq[1].id);
  for (int i = 2; i <= tot; i++) {
    if (seq[i].v != seq[i - 1].v) cnt++, whe[cnt].init();
    a[seq[i].from][seq[i].id] = cnt;
    whe[cnt].v[seq[i].from] = min(whe[cnt].v[seq[i].from], seq[i].id);
  }
  work();
}