H. William and will.i.am
time limit per test
10 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

William and will.i.am are the host and judge, respectively, of a rap battle tournament! The $$$N$$$ contestants will perform on one of two different tracks selected by will.i.am. For each contestant, we know their "rap skill level" on each track. When two players battle on a specific track, the player with higher rap skill level on that track always wins. No two players have the same rap skill level on the same track.

The tournament consists of $$$N-1$$$ battles, and the tournament will proceed as follows:

  1. Randomly select two players still in the tournament.
  2. Choose a track out of the two available ones for the players to battle on.
  3. The player that wins the individual fight will continue on in the tournament, and the loser will be eliminated.
  4. Go back to step 1 and repeat until a single player remains.

William would like to quantitatively measure how "interesting" the tournament structure is relative to other ideas he has, which is directly proportional to the number of possible winners of the tournament. Can you help William find the number of contestants that have a shot at winning it all?

Input

The first line of each test case contains a single integer $$$N$$$ ($$$2 \leq N \leq 10^6$$$), representing the number of tournament contestants. The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$, $$$a_i \neq a_j$$$ for $$$i \neq j$$$), where $$$a_i$$$ is the rap skill level of the $$$i$$$-th contestant on the first track. The third line of each test case contains $$$N$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq n$$$, $$$b_i \neq b_j$$$ for $$$i \neq j$$$), where $$$b_i$$$ is the rap skill level of the $$$i$$$-th contestant on the second track.

Output

Output a single integer representing the number of unique tournament winners out of the $$$N$$$ contestants.

Examples
Input
4
1 2 3 4
1 2 3 4
Output
1
Input
4
1 2 3 4
4 3 1 2
Output
4