1973C - Cat Fox and Double Maximum - CodeForces Solution

import math

def solve():
    n=int(input())
    a=list(map(int,input().split()))
    idx=a.index(n)
    even=a[::2]
    odd=a[1::2]
        odd.sort()
    even.sort()
    d=dict()
    for i,x in enumerate(a):
        d[x]=i
    res=[None]*n
    if idx&1:
        t=n
        for x in odd:
            res[d[x]]=t
            t-=1
        for x in even:
            res[d[x]]=t
            t-=1
    else:
        t=n
        for x in even:
            res[d[x]]=t
            t-=1
        for x in odd:
            res[d[x]]=t
            t-=1
    print(*res)






T=int(input())
for _ in range(T):
    solve()