1983D - Swap Dilemma - CodeForces Solution

def merge_and_count(arr, temp_arr, left, mid, right):
    i = left        j = mid + 1     k = left        inv_count = 0
  
        while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            temp_arr[k] = arr[i]
            i += 1
        else:
                                    temp_arr[k] = arr[j]
            inv_count += (mid-i + 1)
            j += 1
        k += 1
  
        while i <= mid:
        temp_arr[k] = arr[i]
        i += 1
        k += 1
  
        while j <= right:
        temp_arr[k] = arr[j]
        j += 1
        k += 1
  
        for i in range(left, right + 1):
        arr[i] = temp_arr[i]
          
    return inv_count

def merge_sort_and_count(arr, temp_arr, left, right):
    inv_count = 0
    if left < right:
        mid = (left + right)//2
  
        inv_count += merge_sort_and_count(arr, temp_arr, left, mid)
        inv_count += merge_sort_and_count(arr, temp_arr, mid + 1, right)
        inv_count += merge_and_count(arr, temp_arr, left, mid, right)
  
    return inv_count

def inversion_count(arr):
    temp_arr = [0] * len(arr)
    return merge_sort_and_count(arr, temp_arr, 0, len(arr) - 1)

def inversion_parity(arr):
    n = len(arr)
    index_arr = sorted(range(n), key=lambda k: arr[k])
    visited = [False] * n
    parity = 0
    
    for i in range(n):
        if not visited[i]:
            cycle_length = 0
            x = i
            while not visited[x]:
                visited[x] = True
                x = index_arr[x]
                cycle_length += 1
            
            if cycle_length > 0:
                parity ^= (cycle_length - 1) % 2

    return parity

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    
    if inversion_parity(a) % 2 == inversion_parity(b) % 2 and sorted(a) == sorted(b):
        print("YES")
    else:
        print("NO")