← 返回题目列表

Codeforces · 392/D

D. 三个阵列

中文机器翻译题面 查看原题

共有三个数组a、b、c。它们每个都由 n 个整数组成。 SmallY 想要找到三个整数 u、v、w (0 ≤ u、v、w ≤ n),使得以下条件成立:a、b 和 c 并集中出现的每个数字要么出现在 a 的前 u 个元素中,要么出现在 b 的前 v 个元素中,要么出现在 c 的前 w 个元素​​中。当然,SmallY 不希望 u、v 和 w 的数字很大,因此她希望 u + v + w 之和尽可能小。

请帮助她找到 u + v + w 的最小可能总和。

输入

第一行包含一个整数 n (1 ≤ n ≤ 105)。第二行包含 n 个空格分隔的整数 a1, a2, ..., an — 数组 a。第三行以相同的格式包含数组b的描述。第四行以相同的格式包含数组c的描述​​。以下约束成立:1 ≤ ai, bi, ci ≤ 109。

输出

打印一个整数 — u + v + w 的最小可能总和。

示例

输入 #1

3
1 1 101
1 2 1
3 2 1

输出 #1

5

输入 #2

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

输出 #2

5

注意

在第一个示例中,您应该选择 u = 3、v = 0、w = 2。

在第二个示例中,您应该选择 u = 1、v = 3、w = 1。