### COCI 2007/2008, Contest #5

## Task AVOGADRO

Luka is slacking again during chemistry class, while the teacher is explaining Avogadro's law.

Luka first drew a table consisting of 3 rows and N columns. Then he wrote the numbers 1 to N into the first row in arbitrary order, each number appearing exactly once. In the other two rows he also wrote integers between 1 and N, but didn't care how many times a number appeared.

Luka can now delete any set of columns from the table. After doing so, he sorts the numbers in each row in ascending order.

He wants to obtain a table in which all three rows are identical after sorting. Write a program that determines the smallest number of columns he must delete.

### Input

The first line of input contains the integer N (1 ≤ N ≤ 100 000), the number of columns in the table.

The following three lines contain N integers each, separated by single spaces. The numbers will be between 1 and N, and there will be no duplicates in the first row.

### Output

Output the smallest number of columns Luka must delete.

### Scoring

In test cases worth 40% of points, N will be less than 100.

In test cases worth 70% of points, N will be less than 10 000.

### Examples

## Input7 5 4 3 2 1 6 7 5 5 1 1 3 4 7 3 7 1 4 5 6 2 ## Output4 |
## Input9 1 3 5 9 8 6 2 4 7 2 1 5 6 4 9 3 4 7 3 5 1 9 8 6 2 8 7 ## Output2 |

In the first example, Luka needs to delete the second, fourth, sixth and seventh columns. After deleting the columns and sorting each row, all three rows contain the numbers 1, 3 and 5.

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 1.00s

**Memory Limit:** 32M

**Added:** Jan 29, 2009

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

It's quiet in here...