E. Lost Soul
brute force; greedy
You are given two integer arrays \(a\) and \(b\), each of length \(n\).You may perform the following operation any number of times: Choose an index \(i\) \((1 \le i \le n - 1)\), and set \(a_i := b_{i + 1}\), or set \(b_i := a_{i + 1}\). Before performing any operations, you are allowed to choose an index \(i\) \((1 \le i \le n)\) and remove both \(a_i\) and \(b_i\) from the arrays. This removal can be done at most once.Let the number of matches between two arrays \(c\) and \(d\) of length \(m\) be the number of positions \(j\) \((1 \le j \le m)\) such that \(c_j = d_j\).Your task is to compute the maximum number of matches you can achieve.
The first line of the input contains an integer \(t\) \((1 \le t \le 10^4)\) — the number of test cases. The description of each test case follows.The first line contains an integer \(n\) \((2 \le n \le 2 \cdot 10^5)\) — the length of \(a\) and \(b\).The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) \((1 \le a_i \le n)\) — the elements of \(a\).The third line contains \(n\) integers \(b_1, b_2, \dots, b_n\) \((1 \le b_i \le n)\) — the elements of \(b\).It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\).
For each test case, print a single integer — the answer for the test case.
In the first test case, we can do the following: We will choose not to remove any index. Choose index \(3\), and set \(a_3 := b_4\). The arrays become: \(a = [1, 3, 2, 4]\), \(b = [4, 3, 2, 2]\). Choose index \(1\), and set \(a_1 := b_2\). The arrays become: \(a = [3, 3, 2, 4]\), \(b = [4, 3, 2, 2]\). Choose index \(1\), and set \(b_1 := a_2\). The arrays become: \(a = [3, 3, 2, 4]\), \(b = [3, 3, 2, 2]\). Notice that you can perform \(a_i := b_{i + 1}\) and \(b_i := a_{i + 1}\) on the same index \(i\). The number of matches is \(3\). It can be shown that this is the maximum answer we can achieve.In the second test case, we can do the following to achieve a maximum of \(3\): Let's choose to remove index \(5\). The arrays become: \(a = [2, 1, 5, 3, 4]\), \(b = [3, 2, 4, 5, 6]\). Choose index \(4\), and set \(b_4 := a_5\). The arrays become: \(a = [2, 1, 5, 3, 4]\), \(b = [3, 2, 4, 4, 6]\). Choose index \(3\), and set \(a_3 := b_4\). The arrays become: \(a = [2, 1, 4, 3, 4]\), \(b = [3, 2, 4, 4, 6]\). Choose index \(2\), and set \(a_2 := b_3\). The arrays become: \(a = [2, 4, 4, 3, 4]\), \(b = [3, 2, 4, 4, 6]\). Choose index \(1\), and set \(b_1 := a_2\). The arrays become: \(a = [2, 4, 4, 3, 4]\), \(b = [4, 2, 4, 4, 6]\). Choose index \(2\), and set \(b_2 := a_3\). The arrays become: \(a = [2, 4, 4, 3, 4]\), \(b = [4, 4, 4, 4, 6]\). Choose index \(1\), and set \(a_1 := b_2\). The arrays become: \(a = [4, 4, 4, 3, 4]\), \(b = [4, 4, 4, 4, 6]\). In the third test case, it can be shown that we can not get any matches. Therefore, the answer is \(0\).