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\).
3 2 1 2 1 2 2 1 2 2 1 6 1 2 3 4 5 6 2 1 3 5 6 4
2 1 3
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]\).
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor