Avogadro

Time limit1sMemory limit128 MB

Summary
Given a 3xN table where row 1 is a permutation of 1..N, find the minimum number of columns to delete so the three rows can be made identical after sorting each row.
Level

Medium5 of 10

Topics
Greedy, Array, Sorting
Solved
No attempts yet

Problem

Donghyeok really dislikes chemistry. One day in chemistry class the teacher was explaining Avogadro's law, which states that all gases contain the same number of particles (molecules) in the same volume at the same temperature and pressure. In other words, regardless of the kind of gas, the volume a gas occupies at a fixed temperature and pressure is proportional to its number of moles (molecules); doubling the number of moles doubles the volume.

Bored, Donghyeok drew a table of size 3 × N.

  • In the first row he wrote the numbers from 1 to N exactly once each, in an arbitrary order (that is, a permutation of 1..N).
  • In the second and third rows he also wrote N numbers each, again from 1 to N, but here the same number may appear more than once.

Now Donghyeok wants to delete some columns of the table. After the deletions, he sorts each row of the remaining table in ascending order, and he wants the three rows to become identical (after sorting, the three numbers in every column are equal).

Write a program that computes the minimum number of columns Donghyeok must delete.

Input

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

Each of the next three lines contains the N numbers of one row, given from left to right.

Every number is between 1 and N inclusive, and the first row contains each of the numbers 1 through N exactly once.

Output

Print the minimum number of columns that must be deleted on a single line.

Examples2

  1. Example 1

    Input
    7
5 4 3 2 1 6 7
5 5 1 1 3 4 7
3 7 1 4 5 6 2
    Expected output
    4

  2. Example 2

    Input
    9
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
    Expected output
    2