Indian National Olympiad in Informatics

Related:

Online Programming Contest, 12-13 November 2005

IARCS home > OLYMPIAD

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