Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Three Arrays

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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* ≤ 10^{5}). The second line contains *n* space-separated integers *a*_{1}, *a*_{2}, ..., *a*_{n} — 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 ≤ *a*_{i}, *b*_{i}, *c*_{i} ≤ 10^{9}.

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 02:47:18 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|