I caught the sparkle in my mind and got AC1 ! It is a great great experience !

So the basic idea: permute on 3 consecutive items doesn't change the parity of the no. of inversions. Each permutation can only remove 0 or 2 inversions. So we say "YES" when no. of inversion % 2 = = 0. And we use MergeSort to count it in O(nlgn).

ret = 0def merge(arr1, arr2):    global ret    if not arr1: return arr2    if not arr2: return arr1    for v2 in arr2:        arr1.append(v2)        i = len(arr1) - 1        while(i > 0):            if arr1[i] < arr1[i - 1]:                arr1[i - 1],arr1[i] = arr1[i], arr1[i - 1]                i -= 1                ret += 1            else:                break    return arr1def mergeSort(arr):    n = len(arr)    if (n < 2): return arr        return merge(mergeSort(arr[:n//2]), mergeSort(arr[n//2:]))###t = int(input())for _ in range(t):    n = int(input())    arr = list(map(int, input().split()))    ret = 0    mergeSort(arr)    print("YES" if ret % 2 == 0 else "NO")