Split Permutation

★★★★★

3 votes

Bit Manipulation, Greedy algorithm, Basic Programming, Bitmask, Basics of Bit Manipulation

Details

Problem

You are given an array $A$ of distinct integers and another array $B$ which is a permutation of array $A$ . Find the maximum number of segments array $A$ could be split such that within each segment, Array $B$ is a permutation of array $A$ .

INPUT FORMAT

The first line contains an integer, $t$ - denoting the number of test cases.

The first line of each test case contains two integers $n$ - denoting the length of the array $A$ .

The second line of each test case contains $n$ integers — elements of array $A$ .

The second line of each test case contains $n$ integers — elements of array $B$ which is a permutation of array $A$ .

OUTPUT FORMAT

For each test case, print the answer in a new line.

Constraints

$1<=t<=1000$

$1<=n<=10^6$ , sum of $n$ across all test cases <= $10^6$

$-10^{9} ≤ A_i ,B_i≤ 10^{9}$

Array $B$ is a permutation of array $A$ .

Sample Input

3
2
1 2
1 2
2
1 2
2 1
6
1 2 3 4 5 6
2 1 3 5 6 4

Sample Output

2
1
3

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

Test case 1: We split array into following 2 segments - $[0:0]+[1:1]$

such that $A[0:0] = [1]$ is permutation of $B[0:0] = [1]$ and $A[1:1] = [2]$ is permutation of $B[1:1] = [2]$ .

Test case 2: There is no way to split, hence only 1 segment - $[0:1]$

such that $A[0:1] = [1,2]$ is permutation of $B[0:1] = [2,1]$ .

Test case 3: We split array into following 3 segments- $[0:1]+[2:2]+[3:5]$

such that $A[0:1] = [1,2]$ is permutation of $B[0:1] = [2,1]$ , $A[2:2] = [3]$ is permutation of $B[2:2] = [3]$ and $A[3:5] = [4,5,6]$ is permutation of $B[3:5] = [5,6,4]$ .

Contributers:

Ram Gopal

Shruti Sarkar