There are $N$ cities on a circle, numbered $1$ through $N$. For each $i$ ($1 \le i \le N-1$), cities $i$ and $i+1$ are directly connected by a bidirectional road with length $A_i$, and cities $N$ and $1$ are also directly connected by a bidirectional road with length $A_N$. However, we do not know the lengths of some roads.
For each city $i$, we do know that it has an opposite city — formally, there is a city $j \neq i$ such that the clockwise distance between cities $i$ and $j$ is equal to the counterclockwise distance between these cities.
Please find the lengths of all roads in such a way that the above condition is satisfied and the sum of lengths of all roads is minimised.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of the input contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$. For each valid $i$, $A_i = -1$ denotes that the length of road $i$ is unknown.

-----Output-----
For each test case, print a line containing the string "NO" if there is no solution or "YES" otherwise. If a solution exists, print a second line containing $N$ space-separated positive integers — the lengths of all roads in your solution. Each of these integers should be $\le 10^9$. If there are multiple solutions, you may print any one.

-----Constraints-----
- $1 \le T \le 100$
- $3 \le N \le 10^5$
- $1 \le A_i \le 10^9$ or $A_i = -1$ for each valid $i$
- the sum of $N$ for all test cases does not exceed $3\cdot 10^5$

-----Subtasks-----
Subtask #1 (10 points): $N \le 4$
Subtask #2 (20 points): $A_i = \pm 1$ for each valid $i$
Subtask #3 (70 points): original constraints

-----Example Input-----
4
4
1 1 1 1
4
1 1 1 2
4
1 -1 -1 4
4
1 -1 2 -1

-----Example Output-----
YES
1 1 1 1
NO
YES
1 4 1 4
NO

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
# cook your dish here
import math
test=int(input())
for _ in range(test):
 n=int(input())
 l=list(map(int,input().split()))
 f=0
 for i in range(math.ceil(n//2)):
  if n%2==1:
   f=1
   break
  else:
   if l[i]!=l[i+n//2]:
    if min(l[i],l[i+n//2])==-1:
     l[i]=max(l[i],l[i+n//2])
     l[i+n//2]=max(l[i],l[i+n//2])
    else:
     f=1
     break
   else:
    if l[i]==-1:
     l[i]=1
     l[i+n//2]=1
 if f==1:
  print("NO")
 else:
  print("YES")
  print(*l)

# cook your dish here
import math
test=int(input())
for _ in range(test):
 n=int(input())
 l=list(map(int,input().split()))
 f=0
 for i in range(math.ceil(n//2)):
  if n%2==1:
   f=1
   break
  else:
   if l[i]!=l[i+n//2]:
    if min(l[i],l[i+n//2])==-1:
     l[i]=max(l[i],l[i+n//2])
     l[i+n//2]=max(l[i],l[i+n//2])
    else:
     f=1
     break
   else:
    if l[i]==-1:
     l[i]=1
     l[i+n//2]=1
 if f==1:
  print("NO")
 else:
  print("YES")
  print(*l)

import math
for _ in range(int(input())):
 n = int(input())
 l = list(map(int,input().split()))
 f = 0
 for i in range(math.ceil(n//2)):
  if n%2==1:
   f = 1
   break
  else:
   if l[i]!=l[i+n//2]:
    if min(l[i],l[i+n//2])==-1:
     l[i] = max(l[i],l[i+n//2])
     l[i+n//2] = max(l[i],l[i+n//2])
    else:
     f = 1
     break
   else:
    if l[i]==-1:
     l[i] = 1
     l[i+n//2] = 1
 if f==1:
  print("NO")
 else:
  print("YES")
  print(*l)



for _ in range(int(input())):
 n = int(input())
 a = list(map(int, input().split()))
 if n % 2 == 1:
  print("NO")
 else:
  b = a[:n // 2]
  c = a[n // 2:]
  flag = True
  for i in range(n // 2):
   if b[i] != -1 and c[i] != -1:
    if b[i] != c[i]:
     flag = False
     break
   elif b[i] == -1 and c[i] != -1:
    b[i] = c[i]
   elif b[i] != -1 and c[i] == -1:
    c[i] = b[i]
   else:
    c[i] = 1
    b[i] = 1
  if flag:
   print("YES")
   for x in b:
    print(x, end=' ')
   for x in c:
    print(x, end=' ')
   print()
  else:
   print("NO")


# cook your dish here
try:
 for i in range(int(input())):
  n=int(input())
  l=list(map(int,input().split()))
  if(n&1):
   print("NO")
   continue
  b=n//2
  c=0
  for j in range(b):
   if(l[j]>-1 and l[j+b]>-1 and l[j]!=l[j+b]):
    c=1
    break
   elif(l[j]==l[j+b] and l[j]==-1):
    l[j]=1
    l[j+b]=1
   else:
    if(l[j]==-1):
     l[j]=l[j+b]
    elif(l[j+b]==-1):
     l[j+b]=l[j]
  if(c==1):
   print("NO")
  else:
   print("YES")
   for j in range(n-1):
    print(l[j],end=" ")
   print(l[n-1])
except:
 pass


import math
for _ in range(int(input())):
 n = int(input())
 l = list(map(int,input().split()))
 f = 0
 for i in range(math.ceil(n//2)):
  if n%2==1:
   f = 1
   break
  else:
   if l[i]!=l[i+n//2]:
    if min(l[i],l[i+n//2])==-1:
     l[i] = max(l[i],l[i+n//2])
     l[i+n//2] = max(l[i],l[i+n//2])
    else:
     f = 1
     break
   else:
    if l[i]==-1:
     l[i] = 1
     l[i+n//2] = 1
 if f==1:
  print("NO")
 else:
  print("YES")
  print(*l)
  


for _ in range(int(input())):
 N = int(input())
 array = list(map(int, input().split()))
 if N % 2 != 0:
  print('NO')
 else:
  possible = True
  p = N // 2
  for i in range(p):
   if array[i] == -1:
    if array[p+i] == -1:
     array[i] = 1
     array[p+i] = 1
    else:
     array[i] = array[p + i]
   else:
    if array[p+i] == -1:
     array[p + i] = array[i]
    else:
     if array[i] != array[p+i]:
      possible = False
      break
  if possible:
   print('YES')
   print(*array)
  else:
   print('NO')

t=int(input())
for _ in range(t):
 n=int(input())
 a=[int(x) for x in input().split()]
 if n%2!=0:
  print('NO')
  continue
 x=n//2
 possible=True
 for i in range(x):
  if a[i]==-1:
   if a[i+x]==-1:
    a[i]=a[i+x]=1
   else:
    a[i]=a[i+x]
  else:
   if a[i+x]==-1:
    a[i+x]=a[i]
   else:
    if a[i]!=a[i+x]:
     possible=False
     break
 if possible:
  print('YES')
  for x in a:
   print(x,end=' ')
  print()
 else:
  print('NO')

# cook your dish here
for t in range(int(input())):
 n = int(input())
 a = list(map(int, input().split()))
 if n%2 == 0:
  answer = "YES"
  for i in range(n//2):
   if a[i] == a[n//2 + i]:
    if a[i] == -1:
     a[i] = a[n//2+i] = 1
   else:
    if a[i] == -1:
     a[i] = a[n//2+i]
    elif a[n//2 + i] == -1:
     a[n//2 + i] = a[i]
    else:
     answer = "NO"
     break
    
  print(answer)
  if(answer == "YES"): print(" ".join(map(str, a)))
 else:
  print("NO")

t = int(input())
while t>0:
 t -= 1
 n = int(input())
 dis = [int(x) for x in input().split()]
 if n%2 == 1:
  print('NO')
  continue
 mid = n//2
 for i in range(mid):
  if dis[i] == -1 and dis[mid+i] == -1:
   dis[i] = dis[i+mid] = 1
  elif dis[i] == -1:
   dis[i] = dis[i+mid]
  elif dis[i+mid] == -1:
   dis[i+mid] = dis[i]
 flag = True
 for i in range(mid):
  if dis[i] != dis[i+mid]:
   flag = False
   print('NO')
   break
 if flag:
  print('YES')
  for i in range(n):
   print(dis[i], end=' ')
  print()
  
  

T=int(input())
for i in range(T):
 N=int(input())
 A=list(map(int,input().split()))
 x=N//2
 c=0
 if(N%2!=0):
  print("NO")
 else:
  for i in range(x):
   if(A[i]==-1 and A[i+x]==-1):
    A[i]=1
    A[i+x]=1
   elif(A[i]==-1):
    A[i]=A[i+x]
   elif(A[i+x]==-1):
    A[i+x]=A[i]
  for i in range(x):
   if(A[i]!=A[i+x]):
    c=1
    break
  if(c==1):
   print("NO")
  else:
   print("YES")
   print(*A)



t = int(input())
for _ in range(t):
 n = int(input())
 dist = list(map(int, input().split()))
 if n % 2 != 0:
  print("NO")
 else:
  f = 1
  for i in range(n//2):
   if dist[i] != dist[i+n//2] and dist[i] != -1 and dist[i+n//2] != -1:
    f = 0
    break
   elif dist[i] == -1 and dist[i+n//2] == -1:
    dist[i] = 1
    dist[i+n//2] = 1

   else:
    dist[i] = dist[i+n//2] = max(dist[i], dist[i+n//2])

  if f == 0:
   print("NO")
  else:
   print("YES")
   print(' '.join(map(str, dist)))


def m(l,n):
 if n%2 != 0:
  print("NO")
 else:
  c=0
  for i in range (n//2):
   if l[i]==l[n//2+i] :
    if l[i]==-1:
     l[i]=1
     l[n//2+i]=1
     continue
    else:
     continue
   elif l[i]==-1:
    l[i]=l[n//2+i]
    continue
   elif l[n//2+i]==-1:
    l[n//2+i]=l[i]
    continue
   else:
    print("NO")
    c+=1
    break
  if c==0:
   print("YES")
   print(*l)
t=int(input())
while(t):
 n=int(input())
 l=list(map(int,input().split()))
 m(l,n)
 t-=1

for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 flag=0
 if(n%2==1):
  print("NO")
  continue
 for i in range(n//2):
  x=l[i]
  y=l[i+n//2]
  if(x==-1 or y==-1):
   l[i]=max(x,y,1)
   l[i+n//2]=l[i]
  else:
   if(x!=y):
    flag=1
 if(flag==1):
  print("NO")
 else:
  print("YES")
  for i in l:
   print(i,end=" ")
  print("")

for _ in range(int(input())):
 n, ans = int(input()), "YES"
 a = list(map(int, input().split()))
 if n & 1:
  ans = "NO"
 else:
  for i in range(n>>1):
   opp = i + (n>>1)
   if a[i] != -1 and a[opp] != -1 and a[i] != a[opp]:
    ans = "NO"
    break
   elif a[i] == -1 and a[opp] != -1:
    a[i] = a[opp]
   elif a[i] != -1 and a[opp] == -1:
    a[opp] = a[i]
   elif a[i] == -1 and a[opp] == -1:
    a[i] = 1
    a[opp] = 1
 print(ans)
 if ans == "YES":
  print(*a)

import math
t=int(input())
for _ in range(t):
 n=int(input())
 s=0
 a=[int(i) for i in input().split()]
 if n%2!=0:
  print("NO")
 else:
  k=n//2
  f=0
  for i in range(0,k):
   if a[i]!=-1 and a[k+i]!=-1:
    if a[i]!=a[k+i]:
     f=1
     break
    else: 
     f=0
  if f==1:
   print("NO")
  else:
   for i in range(k):
    if a[i]==-1 and a[k+i]==-1:
     a[i]=1
     a[k+i]=1
    elif a[k+i]==-1:
     a[k+i]=a[i]
    else:
     a[i]=a[k+i]
   print("YES")
   for i in range(n):
    print(a[i],end=" ")
   print("")

t=int(input())
for z in range(t):
 n=int(input())
 a=[int(x) for x in input().split()]
 flag=0
 if n%2==0 and (n//2)%2==0:     
  for i in range(n-n//2):
   if a[i]!=-1 and a[i+n//2]!=-1 and a[i+n//2]!=a[i]:
    flag=1
    break
   elif a[i]!=-1 and a[i+n//2]==-1:
    a[i+n//2]=a[i]
   elif a[i]==-1 and a[i+n//2]==-1:
    a[i]=1
    a[i+n//2]=1
   elif a[i]==-1 and a[i+n//2]!=-1:
    a[i]=a[i+n//2]
 elif n%2==0:
  k=1
  for i in a:
   if i!=-1:
    k=i
  for i in range(n-n//2):
   if a[i]!=-1 and a[i+n//2]!=-1 and a[i+n//2]!=a[i]:
    flag=1
    break
   elif a[i]!=-1 and a[i+n//2]==-1:
    a[i+n//2]=a[i]
   elif a[i]==-1 and a[i+n//2]==-1:
    a[i]=k
    a[i+n//2]=k
   elif a[i]==-1 and a[i+n//2]!=-1:
    a[i]=a[i+n//2]
 else:
  print("NO")
  continue
 if sum(a)%2!=0:
  flag=1
 if flag==0:
  print("YES")
  for i in a:
   print(i,end=" ")
  print()
 else:
  print("NO")
  
   


t=int(input())
for z in range(t):
 n=int(input())
 a=[int(x) for x in input().split()]
 flag=0
 if n%2==0 and (n//2)%2==0:     
  for i in range(n-2):
   if a[i]!=-1 and a[i+n//2]!=-1 and a[i+n//2]!=a[i]:
    flag=1
    break
   elif a[i]!=-1 and a[i+n//2]==-1:
    a[i+n//2]=a[i]
   elif a[i]==-1 and a[i+n//2]==-1:
    a[i]=1
    a[i+n//2]=1
   elif a[i]==-1 and a[i+n//2]!=-1:
    a[i]=a[i+n//2]
 elif n%2==0:
  k=1
  for i in a:
   if i!=-1:
    k=i
  for i in range(n-n//2):
   if a[i]!=-1 and a[i+n//2]!=-1 and a[i+n//2]!=a[i]:
    flag=1
    break
   elif a[i]!=-1 and a[i+n//2]==-1:
    a[i+n//2]=a[i]
   elif a[i]==-1 and a[i+n//2]==-1:
    a[i]=k
    a[i+n//2]=k
   elif a[i]==-1 and a[i+n//2]!=-1:
    a[i]=a[i+n//2]
 else:
  print("NO")
  continue
 if sum(a)%2!=0:
  flag=1
 if flag==0:
  print("YES")
  for i in a:
   print(i,end=" ")
  print()
 else:
  print("NO")
  
   


t=int(input())
for z in range(t):
 n=int(input())
 a=[int(x) for x in input().split()]
 flag=0
 if n%2==0 and (n//2)%2==0:     
  for i in range(n-2):
   if a[i]!=-1 and a[i+2]!=-1 and a[i+2]!=a[i]:
    flag=1
    break
   elif a[i]!=-1 and a[i+2]==-1:
    a[i+2]=a[i]
   elif a[i]==-1 and a[i+2]==-1:
    a[i]=1
    a[i+2]=1
   elif a[i]==-1 and a[i+2]!=-1:
    a[i]=a[i+2]
 elif n%2==0:
  k=1
  for i in a:
   if i!=-1:
    k=i
  for i in range(n-2):
   
   if a[i]!=-1 and a[i+2]!=-1 and a[i+2]!=a[i]:
    flag=1
    break
   elif a[i]!=-1 and a[i+2]==-1:
    a[i+2]=a[i]
   elif a[i]==-1 and a[i+2]==-1:
    a[i]=k
    a[i+2]=k
   elif a[i]==-1 and a[i+2]!=-1:
    a[i]=a[i+2]
 else:
  print("NO")
  continue
 if sum(a)%2!=0:
  flag=1
 if flag==0:
  print("YES")
  for i in a:
   print(i,end=" ")
  print()
 else:
  print("NO")
  
   


t=int(input())
for z in range(t):
 n=int(input())
 a=[int(x) for x in input().split()]
 flag=0
 for i in range(n-2):
  if a[i]!=-1 and a[i+2]!=-1 and a[i+2]!=a[i]:
   flag=1
   break
  elif a[i]!=-1 and a[i+2]==-1:
   a[i+2]=a[i]
  elif a[i]==-1 and a[i+2]==-1:
   a[i]=1
   a[i+2]=1
  elif a[i]==-1 and a[i+2]!=-1:
   a[i]=a[i+2]
 if sum(a)%2!=0:
  flag=1
 if flag==0:
  print("YES")
  for i in a:
   print(i,end=" ")
  print()
 else:
  print("NO")
  
   


tc=int(input())
for x in range(tc):
 n=int(input())
 a=[int(x) for x in input().split()]
 if n%2!=0:
  print("NO")
 else:
  a1=a[:n//2]
  a2=a[n//2:]
  t=0
  for i in range(n//2):
   if a1[i]!=-1 and a2[i]!=-1 and a1[i]!=a2[i]:
    print("NO")
    t=1
    break
   else:
    if a1[i]==-1 and a2[i]!=-1:
     a1[i]=a2[i]
    if a2[i]==-1 and a1[i]!=-1:
     a2[i]=a1[i]
    if a1[i]==-1 and a2[i]==-1:
     a1[i]=a2[i]=1
  if t==0:
   print("YES")
   print(*(a1+a2))

T=int(input())
n=0
for i in range(T):
 c=0
 n=int(input())
 A=list(map(int,input().strip().split(" ")))
 if(n%2==1):
  print('NO')
  continue
 for j in range(int(n/2)):
  if A[j]==-1 and A[int(j+n/2)]!=-1:
   A[j]=A[int(j+n/2)]
  elif A[j]!=-1 and A[int(j+n/2)]==-1:
   A[int(j+n/2)]=A[j]
  elif A[j]==-1 and A[int(j+n/2)]==-1:
   A[j]=1 
   A[int(j+n/2)]=1
   continue
 
 
 for j in range(int(n/2)):
  if A[j]!=A[int(j+n/2)]:
   c=1
   break
 if c==1:
  print('NO')
 else:
  print('YES')
  print(" ".join(map(str,A))) 

T=int(input())
n=0
for i in range(T):
 c=0
 n=int(input())
 A=list(map(int,input().strip().split(" ")))
 if(n%2==1):
  print('NO')
  continue
 for j in range(int(n/2)):
  if A[j]==-1 and A[int(j+n/2)]!=-1:
   A[j]=A[int(j+n/2)]
  elif A[j]!=-1 and A[int(j+n/2)]==-1:
   A[int(j+n/2)]=A[j]
  elif A[j]==-1 and A[int(j+n/2)]==-1:
   A[j]=1 
   A[int(j+n/2)]=1
   continue
 
 
 for j in range(int(n/2)):
  if A[j]!=A[int(j+n/2)]:
   c=1
   break
 if c==1:
  print('NO')
 else:
  print('YES')
  print(" ".join(map(str,A))) 

t = int(input())
while t:
 t -= 1
 n = int(input())
 a = list(map(int, input().strip().split()))
 if n % 2:
  print("NO")
 else:
  okay = True
  p = n // 2
  for i in range(p):
   if a[i] == -1 and a[i + p] == -1:
    a[i] = a[i + p] = 1
   elif a[i] == -1:
    a[i] = a[i + p]
   elif a[i + p] == -1:
    a[i + p] = a[i]
   elif a[i] != a[i + p]:
    okay = False
  if okay:
   print("YES")
   for x in a:
    print(x, end = " ")
   print()
  else:
   print("NO")



t=int(input())
for i in range(0,t):
 n=int(input())
 a=[int(i) for i in input().split()]
 if n%2!=0:
  print("NO")
 else:
  i=0
  j=n//2
  flag=0
  while i<(n//2):
   if a[i]==-1 and a[j]!=-1:
    a[i]=a[j]
   elif a[j]==-1 and a[i]!=-1:
    a[j]=a[i]
   elif a[i]==-1 and a[j]==-1:
    a[i]=1
    a[j]=1
   elif a[i]!=a[j]:
    flag=1
    break
   i+=1
   j+=1
  if flag==1:
   print("NO")
  else:
   print("YES")
   print(*a,sep=" ")