ZOJ Problem Set - 2254
Island Country is a very interesting place, in which there are a great many islands. One day Alice and Jim are planning to visit the country. There are so many islands. Which one do they visit at first? Of course all the islands should be visited on. Different islands have different sights, some are interesting and some are boring. The same island is also different for Alice and Jim. One island interesting for Alice may be boring for Jim. They both decide to visit at the islands from the least interesting one (also the most boring one) he or she regards. And then the second least ... at last the most interesting one. Because of their different viewpoints, they cannot enjoy their journey together. The time they visit at each island is arbitrary (you deicde (: ). If they have visited at an island at the same time, they could meet the other. Now your job is to decide the maximal times they could meet.
You will be given the information of all the islands (assuming N islands numbered from 1 to n): two integer sequences a, a, ..., a[n] and b, b, ..., b[n], where a[i] denotes how Alice thinks about the ith island (the larger the more interesting) and b[i] denotes how Jim thinks about it.
For instance n = 3, a = 1, a = 2, a = 3, b = 3, b = 1, b = 2, Alice thinks the first island is the most boring one, so she will visit there first and then the second one and the third one at last. For Jim, he will first visit the second island and then the third and at last the first one.
The first line stands an integer N (0 < N <= 1000), and the second line stands N integers which denote Alice's viewpoints on all the islands. The next line also stands N integers denoting Jim's viewpoints. It's the end when you meet N = 0.
Just one integer on a single line for each case, indicating the maximal times they could meet.
Note: if two islands have the same value on interests, he or she will always visit the former one in numbers.
Author: ZHOU, Kai
Source: ZOJ Monthly, November 2004