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\).
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
Login to unlock the editorial
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