Sereja is hosting his birthday dinner. He invited his N close friends. Let us number the people from 1 to N according to the order in which they arrive at the event. The dinner is being held in long straight corridor in which people sit in a way such that they won't leave any empty space in between two consecutive persons at any given time. 

When a person number i arrives at the corridor, he must go and stand to the immediate right of the person numbered A[i] (if A[i] = 0, then this person just stands at the leftmost end of the line). 

But there is a problem, as there is no space between two consecutive persons at any given time, so for this person to sit, space must be created by moving either all the persons to left of the place to the left one step each, or all the persons to right of the place to the right one step each.  

Now, Sereja is wondering about what could be the minimum number of steps people will take so as to sit in the dinner party. Please find it fast, so that Sereja can peacefully entertain his guests.

-----Input-----
First line of input contain an integer T — the number of test cases. T tests follow.
First line of each test case contain the integer N, and the next line contains N integers — A[1], A[2], ... , A[N].

-----Output-----
For each test case, output a single line with the answer — the minimal number of steps required.

-----Constraints-----
- 1 ≤ T ≤ 100
- 1 ≤ N ≤ 100
- 0 ≤ A[i] < i

-----Example-----
Input:
3
1
0
3
0 0 0
5
0 1 2 1 4

Output:
0
0
3

-----Explanation-----
Example case 3.
- First three persons don't need any steps to sit. The line after the arrangement of these persons will look like [1, 2, 3].  

- When person #4 comes in, he wants to sit to the right of person 1, so we need to either move the first person to the left, or the second and third persons to the right. The first case is clearly better. Now the line will look like [1, 4, 2, 3].  

- When person #5 arrives, he will need to move 2 persons in either case. The final arrangement will be [1, 4, 5, 2, 3]. 

So total number of steps people moved during the entire process is 1 + 2 = 3. So the answer is 3.

Difficulty: interview

Starter code:

Solutions:
a=eval(input())
while(a):

 x=eval(input())
 b=list(map(int,input().split()))
 z=[0]*100
 k=1
 j=0
 c=0
 for i in b:
  
  if i==0:
   
   z.insert(i,k)
   
  else:
   
   if z[z.index(i)+1]==0:
    
    z.insert(j,k)
   else:
    m=z.index(i)
    n=m+1
    p=(len(z)-z.count(0))-n
    c=c+min(n,p)
    
    z.insert(m+1,k)
    
    
  k+=1
  j+=1
  m=0
  n=0
  p=0
  
 print(c)
 
    
    
    
   
  
  
 
 
  


 a-=1


for i in range(eval(input())):
 n = eval(input())
 a=[]
 ans=0
 b = list(map(int, input().split()))
 for j in range(1,n+1):
  temp=b[j-1]
  if(temp==0):
   a.insert(0, j)
  else:
   k=0
   while(a[k]!=temp):
    k+=1
   a.insert(k+1, j)
   ans+=min(k+1,j-k-2)
 print(ans)

t = int(input())
for tt in range(t):
 n = int(input())
 arr = list(map(int, input().split()))
 order = [1]
 ans = 0
 for i in range(1, n):
  num = i + 1
  index = 0
  if arr[i] > 0:
   index = order.index(arr[i])
   ans += min(index + 1, len(order) - index - 1)
   order.insert(index + 1, num)
  else:
   order.insert(0, num)
 print(ans)


for t in range(int(input())): 
 n = int(input())
 s = []
 a = list(map(int,input().split()))
 steps = 0
 for i in range(n):
  if (a[i] == 0):
   s = [i+1] + s
  else:
   pos = s.index(a[i])+1
   steps += min(pos, i-pos)
   s = s[:pos]+[i+1]+s[pos:]
 print(steps)

for t in range(eval(input())):
  n = eval(input())
  v = list(map( int, input().split() ))
  a = []
  ans = 0
  for i in range(n):
    if v[i] == 0 :
      a = [i+1] + a
    else:
      for j in range(len(a)):
        if a[j] == v[i] :
          ans += min( len(a)-j-1, j+1 )
          a = a[:j+1]+[i+1]+a[j+1:]
          break
  print(ans)

for i in range(eval(input())):
 n = eval(input())
 arr = list(map(int,input().split()))
 place = []
 steps = 0
 for i in range(1,n+1):
  pos = arr[i-1]
  if pos==0:
   place.insert(0,i)
  else:
   ind = place.index(pos)
   lef = ind+1
   rig = (i-1)-lef
   if rig==0:
    place.append(i)
   else:
    steps += min(lef,rig)
    place.insert(ind+1,i)
 print(steps)

t = eval(input())
while t != 0:
 cnt = 0
 t -= 1
 n = eval(input())
 a = list(map(int,input().split()))
 s = []
 for i in range(1,n+1):
  pos = a[i-1]
  if pos == 0:
   s.insert(0,i)
  else:
   pos = s.index(a[i-1])
   cnt += min(pos+1, i-2-pos)
   s.insert(pos+1,i)
 print(cnt)


for _ in range(eval(input())):
 n = eval(input())
 ar = list(map(int,input().split()))
 cnt = 0
 ans = []
 for i in range(n):
  if ar[i]==0:
   ans = [i+1] + ans
  else:
   ind = ans.index(ar[i])
   tmp = min(ind+1, len(ans)-ind-1)
   cnt += tmp
   ans = ans[:ind+1] + [i+1] + ans[ind+1:]
 print(cnt)
   


t = eval(input())
for _ in range(t):
 n = eval(input())
 a = [int(x) for x in input().strip().split()]
 ca = []
 ans = 0
 for i, v in enumerate(a):
  if v == 0:
   ans += 0
   ca = [i+1] + ca
  else:
   posOfTarget = ca.index(v) + 1
   leftOfTarget = posOfTarget
   rightOfTarget = len(ca) - posOfTarget
   ans += min(leftOfTarget,rightOfTarget)
   ca = ca[:posOfTarget] + [i+1] + ca[posOfTarget:]
 print(ans)


t = eval(input())
for _ in range(t):
 n = eval(input())
 num = [int(i) for i in input().split()]
 arr = []
 ans=0
 for i in range(1,n+1):
  if(num[i-1]==0):
   arr[0:0]=[i]
  else:
   x = arr.index(num[i-1])+1
   y = len(arr)-x
   ans += min(x,y)
   arr[x:x]=[i]
 print(ans)