#B3928. Tian Ji's Horse Racing

    ID: 11585 Type: Default 1000ms 256MiB

Tian Ji's Horse Racing

Tian Ji's Horse Racing

You are engaged in a classic horse race inspired by Tian Ji's horse racing. Both you and your opponent, Tian Ji, have N horses. The races are held in N rounds. In each round, both sides select one horse to race against each other.

Your horses have speeds \(u_1, u_2, \dots, u_N\), and Tian Ji's horses have speeds \(v_1, v_2, \dots, v_N\). Tian Ji will run his horses in the given order. Since all horses (both yours and Tian Ji's) have distinct speeds, there are no ties. Your task is to rearrange the order in which you race your horses so as to win as many rounds as possible.

Input/Output Format:

Input: The first line contains a single integer N. The second line contains N integers representing the speeds of your horses. The third line contains N integers representing the speeds of Tian Ji's horses, given in the order in which they will race.

Output: Output a single integer, the maximum number of rounds you can win by arranging your horses optimally.

inputFormat

The input consists of three lines:

  1. The first line contains an integer N (the number of horses each player has).
  2. The second line contains N space-separated integers \(u_1, u_2, \dots, u_N\) denoting the speeds of your horses.
  3. The third line contains N space-separated integers \(v_1, v_2, \dots, v_N\) denoting the speeds of Tian Ji's horses in the order they will race.

outputFormat

Output a single integer representing the maximum number of rounds you can win.

sample

3
92 83 71
95 87 74
2