“Jesse, you asked me if I was in the meth business, or the money business… Neither. I’m in the empire business.”
Walter’s sold his stack in Gray Matter Technologies, a company which he deserved half a credit, for peanuts. Now this company is worth a billion dollar company. Walter wants to get it's shares to have his Empire Business back and he founds an opportunity.  
There are $N$ persons having shares $A_1, A_2, A_3, … A_N$ in this company. Walter can buy these shares with their minimum Sold Values. 
Sold Values of a person's share $ i $ $(1 \leq i \leq N) $ with another person's share $ j $ $ (1 \leq j \leq N) $ is equal to $ A_j+|i-j| $. So, a person's share can have $ N $ possible sold values and Walter has to find minimum sold value among them for each person.
Since Walter has to run his meth business also he asks you to find minimum sold value for each person.

-----Input:-----
- First line will contain $T$, number of test cases. Then the testcases follow. 
- The First line of each test case contains a integer $N$.
- The Second line of each test case contains $N$ space integers namely $A_1,A_2,…A_N$.

-----Output:-----
For each test case, output in single line $N$ space integers denoting minimum sold value for each person.

-----Constraints-----
- $1 \leq T \leq 10^5$
- $1 \leq N \leq 2*10^6 $
- $1 \leq A_i \leq 10^9 $
Sum of $N$ over all test cases will not exceed $2*10^6$.

-----Sample Input:-----
2
5
6 5 5 5 2
5
1 2 3 4 5

-----Sample Output:-----
6 5 4 3 2
1 2 3 4 5

-----Explanation-----
For first case:
- Sold value for index $1$:  $6,6,7,8,6$
- Sold value for index $2$:  $7,5,6,7,5$
- Sold value for index $3$:  $8,6,5,6,4$
- Sold value for index $4$:  $9,7,6,5,3$
- Sold value for index $5$:  $10,8,7,6,2$
Minimum sold value for each index will be $6,5,4,3,2$.

Difficulty: interview

Starter code:

Solutions:
# cook your dish here
T=int(input())
for _ in range(T):
 n=int(input())
 arr=list(map(int,input().split()))
 left=[-1 for i in range(n)]
 right=[-1 for i in range(n)]
 min1=float("inf")
 for i in range(n):
  min1=min(arr[i],min1+1)
  left[i]=min1
 min1=float("inf")
 for i in range(n-1,-1,-1):
  min1=min(arr[i],min1+1)
  right[i]=min1
 for i in range(n):
  print(min(left[i],right[i]),end=" ")
 print("",end="\n")

# cook your dish here
t=int(input())
while(t!=0):
 t-=1
 n=int(input())
 fg=list(map(int,input().split()))
 for i in range(1,n):
  fg[i]=min((fg[i-1]+1),fg[i])
 for j in range(n-2,-1,-1):
  fg[j]=min((fg[j+1]+1),fg[j])
 print(*fg)


t=int(input())
for _ in range(t):
 n=int(input())
 l=list(map(int,input().split()))[:n]
 for i in range(1,n):
  l[i]=min((l[i-1]+1),l[i])
 for j in range(n-2,-1,-1):
  l[j]=min((l[j+1]+1),l[j])
 print(*l)

T = int(input())
for _ in range(T):
 N = int(input())
 A = list(map(int, input().split()))
 Llist = [A[0]]
 Rlist = [A[N-1]]
 for i in range(1, N):
  Llist.append(min(Llist[-1]+1, A[i]))
  Rlist.append(min(Rlist[-1]+1, A[N-1-i]))
 print(*[min(Llist[i], Rlist[N-1-i]) for i in range(N)])


for _ in range(int(input())):
 n=int(input())
 l=list(map(int,input().split()))
 left=[]
 mini=float('inf')
 for i in range(n):
  c=min(mini+1,l[i])
  left.append(c)
  mini=c
 mini=float('inf')
 for i in range(n-1,-1,-1):
  left[i]=min(mini+1,left[i])
  mini=min(mini+1,l[i])
 print(*left)

T=int(input())

for _ in range(T):
 n=int(input())
 A=list(map(int,input().split()))
 for i in range(1,n):
  A[i]=min(A[i],A[i-1]+1)

 for i in range(n-2,-1,-1):
  A[i]=min(A[i],A[i+1]+1)
 print(*A)

t = int(input())
for _ in range(t):
 n = int(input())
 arr = list(map(int, input().split()))
 arr_modified = [-1 for _ in range(n)]
 for i in range(n):
  arr_modified[i] = arr[i] + i

 # calculate minRights
 minRights = [arr_modified[-1] for _ in range(n)]
 for i in range(n-2, -1, -1):
  minRights[i] = min(arr_modified[i], minRights[i+1])
 # sold values
 minLeft = float('inf')
 soldValues = [-1 for _ in range(n)]
 for i in range(n):
  soldValues[i] = min(minLeft, minRights[i] - i)
  minLeft = min(minLeft + 1, arr[i] + 1)
 print(' '.join(str(x) for x in soldValues))

for _ in range(int(input())):
 n = int(input())
 *arr, = map(int,input().split())
 ans = [int(1e9)+1]*n
 ans[0] = arr[0]
 for i in range(1,n):
  ans[i] = min(arr[i],ans[i],ans[i-1]+1)
 for i in range(n-1)[::-1]:
  ans[i] = min(arr[i],ans[i],ans[i+1]+1)
 print(*ans)

t=int(input())
for i in range(t):
 n=int(input())
 a=list(map(int,input().split(" ")))
 s=[]
 p=[]
 p.append(a[0])
 for i in range(1,n):
  p.append(min(p[i-1]+1,a[i]))
 s.append(a[n-1])
 j=n-2
 l=0
 while(j>=0):
  s.append(min(s[l]+1,a[j]))
  j=j-1
  l=l+1
 t=s[::-1]
 for k in range(n):
  print(min(t[k],p[k]),end=" ")
 print("")
 
  
  
   
  

for _ in range(int(input())):
 n = int(input())
 *arr, = map(int,input().split())
 ans = [int(1e9)+1]*n
 ans[0] = arr[0]
 for i in range(1,n):
  ans[i] = min(arr[i],ans[i],ans[i-1]+1)
 for i in range(n-2,-1,-1):
  ans[i] = min(arr[i],ans[i],ans[i+1]+1)
 print(*ans)

# cook your dish here
for _ in range(int(input())):
 n = int(input())
 arr = list(map(int, input().split(' ')))
 for i in range(1,n):
  arr[i] = min(arr[i], arr[i-1] + 1)
 for j in range(n-2, -1, -1):
  arr[j] = min(arr[j], arr[j+1] + 1)
 print(*arr)

from itertools import accumulate, count
from operator import add, sub

f = lambda x: accumulate(list(map(sub, x, count())), min)

for s in [*open(0)][2::2]:
 a = *list(map(int, s.split())),
 n = len(a)
 b = f(a)
 c = reversed([*f(reversed(a))])
 print(*(list(map(min, list(map(add, b, count())), list(map(sub, c, count(1 - n)))))))


from itertools import accumulate, count
from operator import add, sub

f = lambda x: accumulate(list(map(sub, x, count())), min)

for s in [*open(0)][2::2]:
 a = *list(map(int, s.split())),
 n = len(a)
 b = f(a)
 c = reversed([*f(reversed(a))])
 print(*(list(map(min, list(map(add, b, count())), list(map(sub, c, count(1 - n)))))))


from itertools import accumulate, count
from operator import sub

f = lambda x: accumulate(list(map(sub, x, count())), min)

for s in [*open(0)][2::2]:
 a = *list(map(int, s.split())),
 n = len(a)
 b = f(a)
 c = reversed([*f(reversed(a))])
 print(*(min(x + i, y + n + ~i) for i, x, y in zip(count(), b, c)))


from itertools import accumulate, count
from operator import sub

f = lambda x: accumulate(list(map(sub, x, count())), min)

for s in [*open(0)][2::2]:
 a = *list(map(int, s.split())),
 n = len(a)
 b = f(a)
 c = reversed([*f(reversed(a))])
 print(*(min(x + i, y + n + ~i) for i, x, y in zip(count(), b, c)))


# cook your dish here
T=int(input())

for _ in range(T):
 n=int(input())
 A=list(map(int,input().split()))
 for i in range(1,n):
  A[i]=min(A[i],A[i-1]+1)

 for i in range(n-2,-1,-1):
  A[i]=min(A[i],A[i+1]+1)
 print(*A)

t=int(input())
for _ in range(t):
 n=int(input())
 ls=list(map(int,input().split()))
 ldp=ls.copy()
 counter=-1
 for i in ldp:
  counter+=1
  if counter==0:
   continue
  ldp[counter]=min(ldp[counter],ldp[counter-1]+1)
 # print(ldp)
 rdp=ldp.copy()
 for j in range(1,n):
  rdp[n-j-1]=min(rdp[n-j-1],rdp[n-j]+1)
 print(*rdp)


# cook your dish here
t=int(input())
for t1 in range(0,t):
 n=int(input())
 a=list(map(int,input().split()))
 left=[]
 right=[]
 for i in range(0,n):
  if i==0:
   left.append((a[i],i))
  else:
   if a[i]< (left[-1][0]+left[-1][1]+1):
    left.append((a[i],0))
   else:
    left.append((left[-1][0],left[-1][1]+1))

 right=[]
 for i in range(n-1,-1,-1):
  if i==n-1:
   right.append((a[i],0))
  else:
   if a[i]< (right[-1][0]+right[-1][1]+1):
    right.append((a[i],0))
   else:
    right.append((right[-1][0],right[-1][1]+1))
 ans=[]
 right=right[::-1]
 #print(left)
 #print(right)
 for i in range(0,n):
  ans.append(min(left[i][0]+left[i][1], right[i][0]+right[i][1]))
 print(*ans)

# cook your dish here
t = int(input())
for _ in range(t):
 n = int(input())
 l = list(map(int,input().split()))
 right = l
 lmin = l[0]
 left = l
 rmin = l[n-1]
 for i in range(0,n):
  left[i] = min(lmin,l[i])
  lmin = left[i]+1
 i = n-1
 while i >= 0:
  right[i] = min(rmin,l[i])
  rmin = right[i] + 1
  i -= 1
 s = ""
 for i in range(n):
  s += str(min(left[i],right[i]))+" "
 print(s.strip())


# cook your dish here
T=int(input())
for _ in range(T):
 n=int(input())
 A=list(map(int,input().split()))
 for i in range(1,n):
  A[i]=min(A[i],A[i-1]+1)
 for i in range(n-2,-1,-1):
  A[i]=min(A[i],A[i+1]+1)
 print(*A)

for _ in range(int(input())):
  n = int(input())
  arr = list(map(int,input().split()))
  for i in range(1,n):arr[i] = min(arr[i],arr[i-1]+1)
  for i in range(n-2,-1,-1):arr[i] = min(arr[i],arr[i+1]+1)
  print(*arr)

t=int(input())
for t1 in range(0,t):
 n=int(input())
 a=list(map(int,input().split()))
 left=[]
 right=[]
 for i in range(0,n):
  if i==0:
   left.append((a[i],i))
  else:
   if a[i]< (left[-1][0]+left[-1][1]+1):
    left.append((a[i],0))
   else:
    left.append((left[-1][0],left[-1][1]+1))

 right=[]
 for i in range(n-1,-1,-1):
  if i==n-1:
   right.append((a[i],0))
  else:
   if a[i]< (right[-1][0]+right[-1][1]+1):
    right.append((a[i],0))
   else:
    right.append((right[-1][0],right[-1][1]+1))
 
 right=right[::-1]
 #print(left)
 #print(right)
 final1=[]
 for i in range(0,n):
  final1.append(min(left[i][0]+left[i][1],a[i]))
 final2=[]
 for i in range(0,n):
  final2.append(min(right[i][0]+right[i][1],a[i]))

 ans=[]
 for i in range(0,n):
  ans.append(min(final1[i],final2[i]))
 print(*ans)

 '''l=a[::]
    for i in range(1,n):
     a[i]=min(a[i],a[i-1]+1)

    for i in range(n-2,-1,-1):
     a[i]=min(a[i+1]+1,a[i])

    if a!=ans:
     print(l)
     print(a)
     #print(left)
     #print(right)
     print(ans)
     print()
    print(a)
    print()
    for i in range(1,n):
     a[i]=min(a[i],a[i-1]+1)

    for i in range(n-2,-1,-1):
     a[i]=min(a[i+1]+1,a[i])
    print(*a)'''