### Indian National Olympiad in Informatics

### Online Programming Contest, 12-13 November 2005

### Basic Division

Problem 1: Conflicting Lists, *(K Narayan Kumar, CMI)*

Our good friend, the king, has the habit of honouring some of the
officers from his Army on the anniversary of his coronation. The king
has two Chief Ministers and each of them insists on having a say in
deciding the list of officers to be honoured. The king asks each
minister to rank the officers in the order of merit. Of course, the
ministers are quite unlikely to order the officers identically.

So, how does the King select the honours list? He realises
that if some *J* officers were chosen and they don't
happen to be the first *J* officers in a minister's list,
then he would know that his opinion has been superseded and that
would make him quite unhappy, and unhappy ministers can make the
king quite unhappy!

Honouring a officer involves giving cash awards, promotions
and so on, all of which costs money and the King would like to
minimise his expenditure. So, he realises that the idea is to
find the smallest set of officers such that, if the set has
*J* elements, then the first *J* elements in both
the lists consist of these *J* officers, though the
ordering may be different in the two lists.

For example, if there are 10 officers, numbered 1,2,...,10, and
the lists handed out by the two ministers orders are:

3 5 7 1 2 4 6 8 9 10

and

1 2 3 4 7 5 6 8 9 10

where the lists are in decreasing order of merit. If the
king choses to honour the officers in the set {1,2,3,4,5,7} then
both ministers would believe that he picked the first 6 officers
from his list. You can check that no set of smaller size has
this property.

Your task is to help the king make his choice.

Input format

The first line of the input contains a single integer *N*,
indicating the number of officers in the King's army. We take the
ministers to be {1,2,...,*N*}. The next two lines each contain
*N* integers, describing the ranking of the officers, in
decreasing order of merit, according to the two ministers.

Output format

A single integer giving the size of the smallest list of officers
he can honour without disappointing either of his ministers.

Test data

You may assume that 1 ≤ *N* ≤ 100000. You may
further assume that in at least 20% of the inputs 1 ≤
*N* ≤ 1000.

Example

We now illustrate input and output formats using the example
described above.

Sample input

10
3 5 7 1 2 4 6 8 9 10
1 2 3 4 7 5 6 8 9 10

Sample output

6