Minimum Scout Visits for Guaranteed Championship

In Kishinev, the capital of Moldova, two football teams, each composed of N players, face off in N one‐on‐one matches, each held in a different stadium. In every match, exactly one player from each team is selected, and each player plays in exactly one match. The winner of a match is the player with the higher skill level – it is guaranteed that the two players’ skills are never equal. Each stadium awards a certain bonus amount to the winner of its match. At the end of all matches the champion is defined as the team whose total bonus (i.e. the sum of bonuses from the stadiums in which they won) exceeds that of the opponent; if both teams gain the same bonus total then there is no champion.

You are the manager of the first team. You know the skill levels of all N players in your team, but you do not initially know the order in which the opposing team’s players (with their respective skill levels) will appear. The opposing team also has N players. A scout is sent to visit the stadiums in order from 1 to N. When the scout visits stadium i, he reports the opponent player’s skill level that will compete in that stadium.

Your goal is to guarantee that your team becomes champion. Since the bonus amounts may vary from stadium to stadium and are awarded only to match winners, the only way to guarantee a championship is to ensure that your team wins strictly more than half of the matches. (In other words, if there are N matches, you must secure at least ⌊N/2⌋+1 wins.)

Because you can assign your players to stadiums in any order once you have enough information, you wish to know the minimum number of stadiums that must be visited by the scout so that, based solely on the reported opponent skill levels in these visited stadiums, you can be sure that there exists an assignment of your players to N stadiums which wins at least ⌊N/2⌋+1 matches. In the remaining (unvisited) stadiums the opponent players are still unknown. However, since you know the entire list of opposing players’ skill levels (but not their order), you can view the set of unvisited opponents as a multiset. You must decide on a strategy that guarantees a championship regardless of how the unvisited opponents are eventually ordered.

Formally, you are given:

• An integer N representing the number of matches.
• An array of N integers, representing the skill levels of your team’s players.
• An array of N integers, representing the skill levels of the opposing team’s players in the order they will appear (i.e. the order in which the scout will report them). Although you do not initially know this order, the complete list is available as input for planning purposes.

Your task is to determine the minimum number of stadiums (i.e. the smallest prefix length k of the opposing array) that the scout must visit so that you can be sure, by optimally assigning your players to the N matches, to win at least ⌊N/2⌋+1 matches. If it is impossible for your team to become champion (i.e. even with full information, you cannot win more than half of the matches), output -1.

Note: You may assume that if an assignment winning at least ⌊N/2⌋+1 matches is possible using the full set of opponent players, then there exists an assignment that guarantees these wins regardless of how the unvisited opponents are eventually ordered. In such a case, it suffices to have the scout visit a number of stadiums such that among the reported opponents, there are at least ⌊N/2⌋+1 players whose skill levels are low enough that they can be beaten by appropriately chosen players from your team.

inputFormat

The input begins with an integer N (1 ≤ N ≤ 10⁵), the number of matches. The second line contains N integers, representing the skill levels of your team’s players. The third line contains N integers, representing the skill levels of the opposing team’s players in the order they will appear (stadium order).

outputFormat

Output a single integer: the minimum number of stadiums that must be visited by the scout so that you can guarantee at least ⌊N/2⌋+1 wins (and hence the championship). If it is impossible to become champion, output -1.

sample

5
3 5 7 9 11
1 4 6 8 10

3