Training Site
Sideways banner


Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 1.5 seconds

Toddy is the new leader of his school's Rock Paper Scissors club, and tomorrow they're having a friendly competition with a rivalling school! Both clubs have exactly N players of varying skill levels, so every player will get to play a single match against some player from the opposing school.

As Toddy is a strategic mastermind, he has managed to obtain the rivalling school's secret lineup, which tells him the order in which their players will play their matches. Toddy knows the skill levels of every player in both schools, and would like to order his own school's lineup in such a way that maximises the total number of games his school will win. Of course, as Rock Paper Scissors is a game of pure skill, in any match between two players, the player with the higher skill level will always win. It is guaranteed that no two players share the same skill level.

Help Toddy find the maximum number of games his club can win, by arranging his lineup optimally.


The first line will contain a single integer, N, the number of players in each school's club (1 \le N \le 100\,000).

The second line will contain N space-separated integers, a_1, a_2, \dots, a_N, the skill levels of the players in Toddy's club, in no particular order (1 \le a_i, b_i \le 1\,000\,000).

The third line will contain N space-separated integers, b_1, b_2, \dots, b_N, the skill levels of the players in the rivalling school's club, in the order that they will play their matches.


You should output a single integer – the maximum number of games Toddy's club can win.


  • Subtask 1 (50%): N \le 1000
  • Subtask 2 (50%): N \le 100\,000

Sample Explanation

In the first sample case, Toddy's club can win at most 3 matches, by ordering his lineup as 3, 8, 5, 1 (against his opponent's lineup of 2, 6, 4, 7). With this lineup, they would win the first three matches, as 3 > 2, 8 > 6, and 5 > 4, but lose the last match, as 1 < 7.

In the second sample case, Toddy's club can only win 1 match, by playing their highest skilled player (7) first, against the player with skill level 6.

  • Sample Input 1

    3 1 8 5
    2 6 4 7

    Sample Output 1

  • Sample Input 2

    4 5 7
    6 8 9

    Sample Output 2