B. Array merging

You are given two arrays 𝑎 and 𝑏 both of length 𝑛 . You will merge† these arrays forming another array 𝑐 of length 2⋅𝑛 . You have to find the maximum length of a subarray consisting of equal values across all arrays 𝑐 that could be obtained.

You are given two arrays a and b both of length n.

You will merge† these arrays forming another array c of length 2⋅n. You have to find the maximum length of a subarray consisting of equal values across all arrays c that could be obtained.

† A merge of two arrays results in an array c composed by successively taking the first element of either array (as long as that array is nonempty) and removing it. After this step, the element is appended to the back of c. We repeat this operation as long as we can (i.e., at least one array is nonempty).

Input

Each test contains multiple test cases. The first line of input contains a single integer t (1 ≤ t ≤ 10⁴) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer n (1 ≤ n ≤ 2⋅10⁵) — the length of the arrays a and b.

The second line of each test case contains n integers a₁, a₂, …, a_n (1 ≤ a_i ≤ 2⋅n) — the elements of array a.

The third line of each test case contains n integers b₁, b₂, …, b_n (1 ≤ b_i ≤ 2⋅n) — the elements of array b.

It is guaranteed that the sum of n across all test cases does not exceed 2⋅10⁵.

Output

For each test case, output the maximum length of a subarray consisting of equal values across all merges.

Example

Input

Output

Note

In the first test case, we can only make c = [2, 2], thus the answer is 2.

In the second test case, since all values are distinct, the answer must be 1.

In the third test case, the arrays c we can make are [1, 2, 1, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 1, 2, 1]. We can see that the answer is 2 when we choose c = [1, 2, 2, 1].

Solution

void solve()
{

    int n;
    cin >> n;

    vi a(n), b(n);
    int mx1 = 0, mx2 = 0, temp = 0;
    mii m1, m2;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i == 0 || a[i] == a[i - 1])
            temp++;
        else
            temp = 1;
        mx1 = max(mx1, temp);
        m1[a[i]] = max(m1[a[i]], temp);
    }
    temp = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
        if (i == 0 || b[i] == b[i - 1])
            temp++;
        else
            temp = 1;
        mx2 = max(mx2, temp);
        m2[b[i]] = max(m2[b[i]], temp);
    }
    int ans = 0;
    for (auto it : m1)
    {
        ans = max(ans, it.second + m2[it.first]);
    }

    for (auto it : m2)
    {
        ans = max(ans, it.second + m1[it.first]);
    }

    cout << ans << endl;
}


#include <bits/stdc++.h>

using namespace std;

#define int long long int
#define F first
#define S second
#define pb push_back
#define si set<int>
#define vi vector<int>
#define pii pair<int, int>
#define vpi vector<pii>
#define vpp vector<pair<int, pii>>
#define mii map<int, int>
#define mpi map<pii, int>
#define spi set<pii>
#define endl "\n"
#define sz(x) ((int)x.size())
#define all(p) p.begin(), p.end()
#define double long double
#define que_max priority_queue<int>
#define que_min priority_queue<int, vi, greater<int>>
#define bug(...) __f(#__VA_ARGS__, __VA_ARGS__)
#define print(a)          \
    for (auto x : a)      \
        cout << x << " "; \
    cout << endl
#define print1(a)    \
    for (auto x : a) \
    cout << x.F << " " << x.S << endl
#define print2(a, x, y)         \
    for (int i = x; i < y; i++) \
        cout << a[i] << " ";    \
    cout << endl
#define scanit(a, n)                             \
    for (ll indexaa = 0; indexaa < n; indexaa++) \
        cin >> a[indexaa];

inline int power(int a, int b)
{
    int x = 1;
    while (b)
    {
        if (b & 1)
            x *= a;
        a *= a;
        b >>= 1;
    }
    return x;
}

template <typename Arg1>
void __f(const char *name, Arg1 &&arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f(const char *names, Arg1 &&arg1, Args &&...args)
{
    const char *comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | ";
    __f(comma + 1, args...);
}

const int N = 200005;

void solve()
{

    int n;
    cin >> n;

    vi a(n), b(n);
    int mx1 = 0, mx2 = 0, temp = 0;
    mii m1, m2;

    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i == 0 || a[i] == a[i - 1])
            temp++;
        else
            temp = 1;
        mx1 = max(mx1, temp);
        m1[a[i]] = max(m1[a[i]], temp);
    }
    temp = 0;
    for (int i = 0; i < n; i++)
    {
        cin >> b[i];
        if (i == 0 || b[i] == b[i - 1])
            temp++;
        else
            temp = 1;
        mx2 = max(mx2, temp);
        m2[b[i]] = max(m2[b[i]], temp);
    }
    int ans = 0;
    for (auto it : m1)
    {
        ans = max(ans, it.second + m2[it.first]);
    }

    for (auto it : m2)
    {
        ans = max(ans, it.second + m1[it.first]);
    }

    cout << ans << endl;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    clock_t z = clock();

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

TagsB. Array mergingCodeForcesC++Codeforces Round 875 (Div. 2)

Raunit Verma

Technical Writer at CodingKaro

Share this on