We have a permutation P = P_1, P_2, \ldots, P_N of 1, 2, \ldots, N.
You have to do the following N - 1 operations on P, each exactly once, in some order:
 - Swap P_1 and P_2.
 - Swap P_2 and P_3.
\vdots
 - Swap P_{N-1} and P_N.
Your task is to sort P in ascending order by configuring the order of operations.
If it is impossible, print -1 instead.

-----Constraints-----
 - All values in input are integers.
 - 2 \leq N \leq 2 \times 10^5
 - P is a permutation of 1, 2, \ldots, N.

-----Input-----
Input is given from Standard Input in the following format:
N
P_1 P_2 \ldots P_N

-----Output-----
If it is impossible to sort P in ascending order by configuring the order of operations, print -1.
Otherwise, print N-1 lines to represent a sequence of operations that sorts P in ascending order.
The i-th line (1 \leq i \leq N - 1) should contain j, where the i-th operation swaps P_j and P_{j + 1}.
If there are multiple such sequences of operations, any of them will be accepted.

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

-----Sample Output-----
4
2
3
1

The following sequence of operations sort P in ascending order:
 - First, swap P_4 and P_5, turning P into 2, 4, 1, 3, 5.
 - Then, swap P_2 and P_3, turning P into 2, 1, 4, 3, 5.
 - Then, swap P_3 and P_4, turning P into 2, 1, 3, 4, 5.
 - Finally, swap P_1 and P_2, turning P into 1, 2, 3, 4, 5.

Difficulty: interview

Starter code:

Solutions:
import sys
 
input = sys.stdin.readline
N = int(input())
P = list(map(int, input().split()))
 
target = 1
ans = []
i = 0
while i < N: 
    if P[i] == target:
        for j in range(i, target-1, -1):
            P[j], P[j-1] = P[j-1], P[j]
            ans.append(j)
    
        target = i+1
        # print("i", i, "target", target)
    i += 1
 
# print(P)
if len(ans) != N-1:
    print(-1)
    return
for i in range(N):
    if P[i] != i+1:
        print(-1)
        return
 
print(*ans, sep="\n")

N = int(input())
P = list(map(int,input().split()))
search, count, flag, ans, pans = 1, 0, 0, [], []
for i in range(N):
    x = P[i]
    if x == search:
        ans += pans[::-1]
        if i < N-1:
            if flag == 0:
                print(-1)
                return
            search, count, flag, pans = i+1, 0, 0, []
            P[i], x = P[i-1], P[i-1]
        
    if x != search:
        if flag == 1:
            print(-1)
            return
        if x > count+search+1:
            flag = 1
        pans.append(i+1)
        count += 1
        
print('\n'.join(map(str,ans)))

import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict, deque, Counter
from itertools import permutations
from math import sqrt, gcd
from functools import reduce
from sys import stdin
from bisect import bisect_right


def get_min(p):
    n = len(p)
    ret = [[] for _ in range(n)]
    for i in reversed(list(range(n))):
        if i == n - 1:
            ret[i] = [i, p[i]]
        elif p[i] < ret[i + 1][1]:
            ret[i] = [i, p[i]]
        else:
            ret[i] = ret[i + 1]
    return ret

def solve(n, p):
    p2 = get_min(p)
    # print(p2)
    left = 0
    ret = []
    while left < n - 1:
        if p[left] < p2[left + 1][1]:
            left += 1
            continue
        right, m = p2[left + 1]
        for i in reversed(list(range(left, right))):
            p[i], p[i + 1] = p[i + 1], p[i]
            ret.append(i + 1)
        for i in range(left, right):
            if i + 1 != p[i]:
                return False
        left = right
    if len(ret) != n - 1:
        return False
    return ret



n = int(input())
p = list(map(int, input().split()))
ans = solve(n, p)
if ans:
    assert len(ans) == n - 1
if ans:
    for a in ans:
        print(a)
else:
    print((-1))



import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    P = list(map(int, input().split()))
    D = defaultdict(int)
    for num in range(n):
        D[P[num]] = num
    res = []
    used = set()
    for num in range(1, n + 1):
        idx = D[num]
        while idx + 1 != num:
            if idx + 1 > num:
                swap = P[idx - 1]
                if idx in used:
                    print(-1)
                    return
                P[idx - 1] = P[idx]
                P[idx] = swap
                used.add(idx)
                res.append(idx)
            else:
                swap = P[idx + 1]
                if idx + 2 in used:
                    print(-1)
                    return
                P[idx + 1] = P[idx]
                P[idx] = swap
                used.add(idx + 2)
                res.append(idx + 2)
            D[num] = D[swap]
            D[swap] = idx
            idx = D[num]
            if len(used) > n - 1:
                print(-1)
                return
    if len(res) != n - 1:
        print(-1)
        return

    print(*res, sep="\n")


def __starting_point():
    resolve()

__starting_point()

n = int(input())
p = list(map(lambda x:int(x)-1,input().split()))

q = [0]*n
for i in range(n):
    q[p[i]] = i

ans = []
i = 0
while i<n:
    idx = q[i]
    if i<idx:
        for j in range(idx-1,i-1,-1):
            p[j],p[j+1] = p[j+1],p[j]
            ans.append(str(j+1))
        i = idx
    else:
        i += 1
if len(ans)==n-1 and all([p[i]==i for i in range(n)]):
    print("\n".join(ans))
else:
    print(-1)

from collections import deque
import sys

n = int(input())
p = list(map(int, input().split()))

stack = deque([])
memo = [0] * (n-1)

for i in range(n-1):
    if p[i] > (i + 1) and p[i+1] < (i + 2):
        stack.append(i)
        memo[i] = 1

ans = []

while stack:
    i = stack.pop()
    if memo[i] == 2:
        # print('p1')
        print((-1))
        return
    p[i], p[i+1] = p[i+1], p[i]
    memo[i] = 2
    ans.append(i+1)

    if i > 0 and p[i-1] > i and p[i] < (i+1) and memo[i-1] == 0:
        stack.append(i-1)
        memo[i-1] = 1

    if i+2 < n and p[i+1] > (i+2) and p[i+2] < (i+3) and memo[i+1] == 0:
        stack.append(i+1)
        memo[i+1] = 1

# print(p)
# print(ans)

if len(ans) != n-1:
    # print('p2')
    print((-1))
    return

f = 1

for i in range(n):
    if p[i] != i+1:
        f = 0
        break

if f:
    for ansi in ans:
        print(ansi)
else:
    # print('p3')
    print((-1))



n = int(input())
p = list(map(int, input().split()))

ans, tmp, res = [], [], []
lst = [i + 1 for i in range(n)]
for i in range(n):
    if i != 0:
        tmp.append(i)
    if p[i] - 1 == len(ans) or i == n - 1:
        res += [p[i]] + p[len(ans):i - 1]
        ans += tmp[::-1]
        tmp = []
        p[i] = p[i - 1]
    if i == n - 1:
        res += [p[i]]
print(*(ans if res == lst else[-1]), sep='\n')


N = int(input())
P = list(map(int, input().split()))

indexes = [x for x in range(N + 1)]
for i in range(N):
    indexes[P[i]] = i

moves = {}
for i in range(1, N):
    moves[i] = False

conf = []
for i in range(1, N+1):
    while indexes[i] != i - 1:
        if moves[indexes[i]] is True:
            print((-1))
            return
        conf.append(indexes[i])
        moves[indexes[i]] = True
        
        a, b = P[indexes[i] - 1], P[indexes[i]]
        P[indexes[i] - 1], P[indexes[i]] = b, a
        indexes[b], indexes[a] = indexes[a], indexes[b]

if not all(moves.values()):
    print((-1))
else:
    print(("\n".join(map(str,conf))))



n = int(input())
p = list(map(int,input().split()))
i = 0
ans = []
target = 1
while i < n:
    if p[i] == target:
        for j in range(i,target-1,-1):
            p[j],p[j-1]= p[j-1],p[j]
            ans.append(j)
        target = i+1
    i += 1

if len(ans)!=n-1:
    print((-1))
elif p != [i for i in range(1,n+1)]:
    print((-1))
else:
    for j in ans:
        print(j)


def main():
    N=int(input())
    pos={}
    P=list(map(int,input().split()))
    for i in range(N):
        pos[P[i]]=i
    end=N
    steps=[]
    while(end>1):
        if(pos[end]<(end-1)):
            start=pos[end]
            for j in range(start,end-1):
                pos[P[j]]=j+1
                pos[P[j+1]]=j
                
                temp=P[j]
                P[j]=P[j+1]
                P[j+1]=temp

                steps.append(j+1)
            end=start+1
        elif(pos[end]>(end-1)):
            break
        else:
            end-=1
    flag=True
    for i in range(N):
        if(P[i]!=(i+1)):
            flag=False
            break
    if(flag):
        if(len(steps)!=(N-1)):
            print((-1))
        else:
            for i in range(len(steps)):
                print((steps[i]))
    else:
        print((-1))
def __starting_point():
    main()

                
                

__starting_point()

import numpy as np
def main():
    n = int(input())
    P = np.fromstring(input(), np.int64, sep=' ')
    D = np.arange(1, n+1) - P
    if np.any(D == 0) or D[D > 0].sum() != n-1:
        print((-1))
        return
    if np.any(np.diff(P[D<0]) < 0) or np.any(np.diff(P[D>0]) < 0):
        print((-1))
        return
    for i in np.nonzero(D>0)[0]:
        j = i
        for _ in range(D[i]):
            print(j)
            j -= 1

def __starting_point():
    main()

__starting_point()

N, *P = map(int, open(0).read().split())

A = []

cur = 1
for i in range(N):
    if P[i] == cur:
        A += reversed(range(cur, i + 1))
    elif P[i] != i + 2:
        if i + 1 == N or P[i + 1] != cur:
            print(-1)
            return
        A += reversed(range(cur, i + 2))
        P[i + 1] = P[i]
        cur = i + 2

for a in A:
    print(a)

from collections import deque
N = int(input())
P = list(map(int, input().split()))
if P==list(range(2,N+1))+[1]:
  print(*list(range(N-1,0,-1)), sep='\n')
  return
ans = []
d = deque([(0,N-1)])
while len(d):
  left, right = d.popleft()
  n = right-left+1
  if n==1:
    continue
  if n==2:
    if P[left]==left+1 and P[right]==right+1:
      print(-1)
      break
    ans.append(left+1)
    continue
  min_a = 10**7
  max_a = -1
  for i in range(n-1):
    if min(min_a, P[left+i+1]) == left+1 and max(max_a, P[left+i+1]) == left+1+i:
      P[left+i], P[left+i+1] = P[left+i+1], P[left+i]
      d.append((left, left+i))
      d.append((left+i+1, right))
      ans.append(left+i+1)
      break
    min_a = min(min_a, P[left+i])
    max_a = max(max_a, P[left+i])
  else:
    print(-1)
    break
else:
  print(*ans, sep='\n')

n = int(input())
p = list(map(int, input().split()))

unswapped = [True] * n
swap_count = 0
swap_order = []
now = 1

for i in range(1, n):
    if p[i] == now:
        for j in range(i, now - 1, -1):
            if unswapped[j]:
                unswapped[j] = False
                swap_count += 1
                swap_order.append(j)
                p[j], p[j-1] = p[j-1], p[j]
            else:
                print(-1)
                return
        now = i + 1

for i in range(n):
    if p[i] != i + 1:
        print(-1)
        return

if swap_count == n - 1:
    print(*swap_order, sep="\n")
else:
    print(-1)

N=int(input())
*P, = map(int,input().split())
 
Q = [0]*(N+1)
for i,p in enumerate(P,1):
    Q[p] = i
    
ans = []
i = 1
while(i < N) :
    j = Q[i]
    if j<=i:break
    for k in range(j-1, i-1,-1):
        ans.append(k)
        P[k],P[k-1] = P[k-1],P[k]
    i = j

if len(ans)==N-1:
    if P == list(range(1,N+1)) :
        for out in ans:
            print(out)
    else :
        print(-1)
else :
    print(-1)

import sys
readline = sys.stdin.readline

N = int(readline())
P = list(map(int,readline().split()))

# P[i] > P[i + 1]となっているところを交換するのを繰り返す

# 交換できるキーの集合
# 交換できないキーの集合
# を持つ
# 交換できるキーの集合を一つ見て、交換する
# 交換した結果i - 1, i + 1がそれぞれ交換可能かを確認する
# 交換可能かどうかの結果が変わっていたら、集合間で移動を行う
# 全てのキーが使用されて且つPが昇順になっていたら成功

can = set()
can_not = set()
done = set()
ans = []
for i in range(N - 1):
  if P[i] > P[i + 1]:
    can.add(i)
  else:
    can_not.add(i)

for i in range(N - 1):
  if len(can) == 0: # 所要回数の交換ができない
    print(-1)
    return
  i = can.pop() # 要素を取り出し
  P[i], P[i + 1] = P[i + 1], P[i] # 交換する
  ans.append(i)
  done.add(i)
  # この結果、i - 1とiが交換可能になっているかを確認する
  if i - 1 >= 0 and i - 1 not in done:
    if P[i - 1] > P[i]:
      if i - 1 not in can:
        can.add(i - 1)
        can_not.remove(i - 1)
    else:
      if i - 1 in can:
        can.remove(i - 1)
        can_not.add(i - 1)
  if i + 2 < N and i + 1 not in done:
    if P[i + 1] > P[i + 2]:
      if i + 1 not in can:
        can.add(i + 1)
        can_not.remove(i + 1)
    else:
      if i + 1 in can:
        can.remove(i + 1)
        can_not.add(i + 1)
        
# 所要回数の交換が実施されたので、この時点でPが昇順になっているかを確認
for i in range(N - 1):
  if P[i] > P[i + 1]:
    print(-1)
    return
    
for a in ans:
  print(a + 1)

n = int(input())
p = list(map(lambda x:int(x)-1,input().split()))

q = [0]*n
for i in range(n):
    q[p[i]] = i

ans = []
i = 0
while i<n:
    idx = q[i]
    if i<idx:
        for j in range(idx-1,i-1,-1):
            p[j],p[j+1] = p[j+1],p[j]
            ans.append(str(j+1))
        i = idx
    else:
        i += 1
if len(ans)==n-1 and all([p[i]==i for i in range(n)]):
    print("\n".join(ans))
else:
    print(-1)

N = int(input())
P = list(map(int,input().split()))
search, before, count, flag, ans, pans = 1, 0, 0, 0, [], []
for i in range(N):
    x = P[i]
    if x == search:
        if i < N-1 and flag == 0:
            print(-1)
            return
        ans += pans[::-1]
        before, search, count, flag, pans = search, i+1, 0, 0, []
        P[i], x = P[i-1], P[i-1]
    if x != search:
        if flag == 1:
            print(-1)
            return
        if x == count+search+1:
            flag = 0
        if x > count+search+1:
            flag = 1
        pans.append(i+1)
        count += 1
    #print(i,x,pans)
print('\n'.join(map(str,ans)))

n=int(input())
p=list(map(int,input().split()))
ans=[]
tmp=1
for i in range(n-1):
    if p[i]==tmp:
        for j in range(i, tmp-1, -1):
            p[j], p[j-1]=p[j-1], p[j]
            ans.append(j)
        tmp=i+1
for j in range(n-1, tmp-1, -1):
    p[j], p[j-1]=p[j-1], p[j]
    ans.append(j)

for i, p in enumerate(p,1):
    if i!=p:
        ans=-1
if ans==-1:
    print(ans)
else:
    print(*ans, sep = "\n")

n = int(input())
p = list(map(int, input().split()))

ans, tmp, res = [], [], []
for i in range(n):
    if i != 0:
        tmp.append(i)
    if p[i] - 1 == len(ans):
        res += [p[i]] + p[len(ans):i - 1]
        ans += tmp[::-1]
        tmp = []
        p[i] = p[i - 1]
else:
    res += [p[i]] + p[len(ans):-1]
    ans += tmp[::-1]
print(*(ans if res == [i + 1 for i in range(n)] else[-1]), sep='\n')



icase=0
if icase==0:
    n=int(input())
    p=list(map(int,input().split()))

for i in range(n):
    p[i]-=1

po=[0]*n
for i in range(n):
    po[p[i]]=i
    
s=[i for i in range(n-1)]
pa=[i for i in range(n)]

s=set(s)
ans=[]
#print("po:",po)
#print(p)

yn=""
for i in range(n):
#    print("i:",i,"po[i]:",po[i])
    if po[i]>i:
        for ii in range(po[i],i,-1):
#            print(p[ii],p[ii-1])
            po[p[ii]],po[p[ii-1]]=ii-1,ii
            p[ii],p[ii-1]=p[ii-1],p[ii]
#            print("ii:",ii,"p",p,"po:",po)
            if ii-1 in s:
                s.remove(ii-1)
                ans.append(ii)
            else:
                yn="no"
                break
            if len(s)==0:
                break
    elif po[i]<i:
        for ii in range(po[i],i,1):
            po[p[ii]],po[p[ii+1]]=ii+1,ii
            p[ii],p[ii+1]=p[ii+1],p[ii]
#            print("ii:",ii,"p",p,"po:",po)
#    print("i:",i,p)
            if ii-1 in s:
                s.remove(ii-1)
                ans.append(ii)
            else:
                yn="no"
                break
            if len(s)==0:
                break
    if yn=="no" or len(s)==0:
        break
    
if p==pa and len(s)==0:
    for ansi in ans:
        print(ansi)
else:
    print((-1))
    


N = int(input())
P = list(map(int, input().split()))
ans = []
left = 0
while left<N-1:
  if P[left]==left+1:
    print(-1)
    return
  for i in range(left+1,N):
    if P[i]==left+1:
      for j in range(i,left,-1):
        ans.append(j)
        P[j-1], P[j] = P[j], P[j-1]
      new_left = i
      break
  for i in range(left, new_left):
    if P[i]!=i+1:
      print(-1)
      return
  left = new_left
print(*ans, sep='\n')


n = int(input())
p = list(map(int, input().split()))

ans, tmp, res = [], [], []
lst = [i + 1 for i in range(n)]
for i in range(n):
    if i > 0:
        tmp.append(i)
    if p[i] - 1 == len(ans) or i == n - 1:
        res += [p[i]] + p[len(ans):i - 1]
        ans += tmp[::-1]
        tmp, p[i] = [], p[i - 1]
res += [p[i]]
print(*(ans if res == lst else[-1]), sep='\n')


N=int(input())
P=list(map(int,input().split()))

t = 1
ans = []
for i in range(N):
  if P[i] == t:
    for j in range(i, t-1, -1):
      P[j], P[j-1] = P[j-1], P[j]
      ans.append(j)
    t = i + 1

for i in range(N):
  if i+1 != P[i]:
    print(-1)
    return
if len(ans) == N-1:
  for x in ans:
    print(x)
else:
  print(-1)

import numpy as np
n = int(input())
p = list(map(int, input().split()))
p=p-np.ones((n,))
swapped=np.zeros((n-1,))
now=0
noc=1

for now in range(0,n-1):
  for i in range(now,n):
    if (p[i]==now):
      if(p[i]<i):
        for j in range(int(i-1),int(p[i]-1),-1):
          if swapped[j]!=0:
            print(-1)
            return
          kari=p[j]
          p[j]=p[j+1]
          p[j+1]=kari
          swapped[j]=noc  
          noc+=1
      break
for i in range(0,n-1):
  if int(swapped[i])==0:
    print(-1)
    return
for i in range(0,n-1):
  print(int(swapped[i])) 

# swap(ps[right-1], ps[right]), swap(ps[right-2], ps[right-1]), ... swap(ps[left], ps[left+1])
def f(left, right, ps, acc):
    for i in range(right - 1, left - 1, -1):
        ps[i], ps[i + 1] = ps[i + 1], ps[i]
        acc.append(i + 1)

def solve(n, ps, acc):
    for i in range(n):
        if ps[i] == i + 1:
            return False

    cur_number = 1
    prev_idx = 0
    cur_idx = 0
    while cur_idx < n:
        if ps[cur_idx] == cur_number:
            f(prev_idx, cur_idx, ps, acc)
            prev_idx = cur_idx
            cur_number = cur_idx + 1
        cur_idx += 1

    for i in range(n):
        if ps[i] != i + 1:
            return False

    return True

def __starting_point():
    n = int(input())
    ps = [int(p) for p in input().split()]
    acc = []
    if not solve(n, ps, acc):
        print((-1))
    else:
        for line in acc:
            print(line)

__starting_point()

n = int(input())
p = list(map(int, input().split()))

ans, tmp, res = [], [], []
for i in range(n):
    if i != 0:
        tmp.append(i)
    if p[i] - 1 == len(ans):
        res += [p[i]] + p[len(ans):i - 1]
        ans += tmp[::-1]
        tmp = []
        p[i] = p[i - 1]
else:
    res += [p[i]] + p[len(ans):i - 1]
    ans += tmp[::-1]
print(*(ans if res == [i + 1 for i in range(n)] else[-1]), sep='\n')


import sys
 
input = sys.stdin.readline
N = int(input())
P = list(map(int, input().split()))
 
target = 1
ans = []
for i in range(N):
    if P[i] == target:
        for j in range(i, target-1, -1):
            P[j], P[j-1] = P[j-1], P[j]
            ans.append(j)
    
        target = i+1
        # print("i", i, "target", target)
    
# print(P)
if len(ans) != N-1:
    print(-1)
    return
for i in range(N):
    if P[i] != i+1:
        print(-1)
        return
 
print(*ans, sep="\n")

import sys
 
input = sys.stdin.readline
N = int(input())
P = list(map(int, input().split()))
 
target = 1
ans = []
i = 0
while i < N: 
    if P[i] == target:
        for j in range(i, target-1, -1):
            P[j], P[j-1] = P[j-1], P[j]
            ans.append(j)
    
        target = i+1
        # print("i", i, "target", target)
    i += 1
 
# print(P)
if len(ans) != N-1:
    print(-1)
    return
for i in range(N):
    if P[i] != i+1:
        print(-1)
        return
 
print(*ans, sep="\n")

N = int(input())
P = list([int(x) - 1 for x in input().split()])
pos = {P[i]: i for i in range(N)}
cur = 0
ans = []
for i in range(N):
    if pos[i] == i:
        continue
    start = pos[i]
    for j in range(start, cur, -1):
        ans.append(j)
        pos[P[j]], pos[P[j - 1]] = pos[P[j - 1]], pos[P[j]]
        P[j], P[j - 1] = P[j - 1], P[j]
    cur = max(cur, start)
if all(i == P[i] for i in range(N)) and cur == N - 1:
    print(("\n".join(map(str, ans))))
else:
    print((-1))


N = int(input())
P = list([int(x) - 1 for x in input().split()])
RP = [0] * N
for i, p in enumerate(P):
    RP[p] = i

used = [False] * N

idx = 0

used = [False] * (N - 1)
record = []
ok = True

while ok and idx != N:
    cur = RP[idx]
    # print(cur, idx)
    while ok and cur != idx:
        if cur > idx:
            if used[cur - 1]:
                ok = False
                break
            record.append(cur)
            used[cur - 1] = True
            RP[idx], RP[P[cur - 1]] = RP[idx] - 1, RP[P[cur - 1]] + 1
            P[cur], P[cur - 1] = P[cur - 1], P[cur]

            cur -= 1
        else:
            if used[cur]:
                ok = False
                break
            record.append(cur + 1)
            used[cur] = True
            RP[idx], RP[P[cur + 1]] = RP[idx] + 1, RP[P[cur + 1]] - 1
            P[cur], P[cur + 1] = P[cur + 1], P[cur]

            cur += 1

        # print(P, RP)
    idx += 1

if ok and len(record) == N - 1:
    for ans in record:
        print(ans)
else:
    print((-1))
#
# print(used)


import random
def solve(N,P):
    operation = []
    target = 1
    confirmed_start = 0 
    confirmed_end = -1

    for i in range(N):
        if P[i] == target:
            for j in range(i-1, confirmed_start-1, -1): 
                P[j], P[j+1] = P[j+1], P[j]
                operation.append(j+1)
            
            confirmed_end = i
            for j in range(confirmed_start, confirmed_end):
                if P[j] != j+1:
                    print(-1)
                    return
            
            target = i+1
            confirmed_start = confirmed_end

    if confirmed_end != N-1:
        print(-1)
        return

    print(*operation, sep='\n')

def __starting_point():
    # N = 10
    # nums = list(range(1,N+1))
    # idx = list(range(N-1))
    # order = random.sample(idx, len(idx))
    # for o in order:
    #     nums[o], nums[o+1] = nums[o+1], nums[o]

    # print(nums)
    # solve(N, nums)

    N = int(input())
    P = list(map(int,input().split()))
    solve(N,P)

__starting_point()

def solve(n, p):
    D = {x: i for i, x in enumerate(p)}
    S = set()
    ans = []
    for x in range(1, n+1):
        for j in range(D[x]-1, x-2, -1):
            a, b = p[j], p[j+1]
            p[j+1], p[j] = p[j], p[j+1]
            D[a], D[b] = D[b], D[a]
            ans.append(j+1)
            if j in S:
                return -1
            S.add(j)
    if len(ans) != n-1:
        return -1
    return "\n".join(map(str, ans))

n = int(input())
p = list(map(int, input().split()))
print(solve(n, p))

import sys
 
input = sys.stdin.readline
N = int(input())
P = list(map(int, input().split()))
 
target = 1
ans = []
i = 0
while i < N: 
    if P[i] == target:
        for j in range(i, target-1, -1):
            P[j], P[j-1] = P[j-1], P[j]
            ans.append(j)
    
        target = i+1
        # print("i", i, "target", target)
    i += 1

# print(P)
if len(ans) != N-1:
    print(-1)
    return
for i in range(N):
    if P[i] != i+1:
        print(-1)
        return
 
print(*ans, sep="\n")

N = int(input())
A = list(map(int, input().split()))
for i in range(N):
    A[i] -= 1
X = [0]*N
for i in range(N):
    X[A[i]] = i
P = [False]*(N-1)
now = 0
F = []
flg = True
while now < N:
    if X[now] != now:
        F.append(X[now])
        X[now] -= 1
        if P[X[now]]:
            flg = False
            break
        P[X[now]] = True
        A[X[now]], A[X[now]+1] = A[X[now]+1], A[X[now]]
        X[A[X[now]+1]] += 1
    else:
        now += 1
if flg and len(F) == N - 1:
    for i in range(N-1):
        print(F[i])
else:
    print(-1)

def LI():return list(map(int,input().split()))
def II():return int(input())
def LI():return list(map(int,input().split()))
def II():return int(input())
def yes():return print("Yes")
def no():return print("No")
INF=float("inf")
from collections import deque, defaultdict, Counter
from heapq import heappop, heappush
from itertools import product, combinations
from functools import reduce, lru_cache
from math import pi, gcd
from decimal import Decimal

mod=998244353
mod=10**9+7

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

class Unionfind:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]


# フレンズさんの模範回答
class dsu:
	def __init__(self,n):
		self.cnt=[1]*n
		self.root=list(range(n))
	def unite(self,x,y):
		x=self.root[x]
		y=self.root[y]
		if x!=y:
			if self.cnt[x]<self.cnt[y]:
				x,y=y,x
			self.cnt[x]+=self.cnt[y]
			self.root[y]=x
		return x
	def leader(self,x):
		if self.root[x]==x:
			return x
		self.root[x]=self.leader(self.root[x])
		return self.root[x]
 


n=II()
p=LI()

ans=[]
ansset=set()
ind_list=[-1]*(n+1)
for ind,num in enumerate(p):
    ind_list[num]=ind
for i in range(1,n+1):
    a=ind_list[i]

    while a>i-1:
        p[a],p[a-1]=p[a-1],p[a]
        ind_list[p[a]]+=1
        ans.append(a)
        if a in ansset:
            print(-1)
            return
        ansset.add(a)
        a-=1
if p==list(range(1,n+1)):
    if len(ans)==n-1:
        for val in ans:
            print(val)
        return

print(-1)
    
    

def main():
  import sys
  input=sys.stdin.readline
  n=int(input())
  p=list(map(int,input().split()))
  c=[-1]*n
  for i in range(n):
    p[i]-=1
    c[p[i]]=i
  r=[False]*(n-1)
  ans=[]
  for i in range(n):
    j=c[i]
    while j!=i:
      if r[j-1]:
        print(-1)
        return
      ans.append(j)
      r[j-1]=True
      p[j-1],p[j]=p[j],p[j-1]
      c[p[j]]=j
      c[p[j-1]]=j-1
      j-=1
  for i in r:
    if not i:
      print(-1)
      return
  for i in ans:
    print(i)
main()

N = int(input())
P = list(map(int,input().split()))
search, count, flag, ans, pans = 1, 0, 0, [], []
for i in range(N):
    x = P[i]
    if x == search:
        ans += pans[::-1]
        if i < N-1:
            if flag == 0:
                print(-1)
                return
            search, count, flag, pans = i+1, 0, 0, []
            P[i], x = P[i-1], P[i-1]
        
    if x != search:
        if flag == 1:
            print(-1)
            return
        if x > count+search+1:
            flag = 1
        pans.append(i+1)
        count += 1
        
for k in ans:
    print(k)

n = int(input())
P = list(map(int, input().rstrip().split(" ")))

A = [i+1 for i in range(n)]
B = [1 for i in range(n)]
stack = []
isOK = True

for i, a in enumerate(A):
    
    if(isOK == False):
        break
    
    p = P[i]
    j = (p - 1)
    
    while(i+1 <= j):
        if(B[j] < 0):
            isOK = False
            break
        stack.append(j)
        B[j] -= 1
        A[j-1], A[j] = A[j], A[j-1]
        j -= 1

B[0] = 0
for i in range(n):
    a = A[i]
    b = B[i]
    p = P[i]
    if(a != p) or(b != 0):
        isOK = False

if(isOK):
    for i in range(n-1):
        print(stack.pop())
else:
    print(-1)

N = int(input())
P = list(map(lambda x: int(x) - 1, input().split()))

D = [0] * N

for i in range(N):
    D[P[i]] = i

lt = 0
used = [0] * N
res = []

for i in range(N):
    if used[i]:
        continue
    if lt > D[i]:
        print(-1)
        break
    rt = D[i]
    for j in range(lt, rt)[::-1]:
        D[P[j]], D[P[j + 1]] = D[P[j + 1]], D[P[j]]
        P[j], P[j + 1] = P[j + 1], P[j]
        res.append(j + 1)
    for j in range(lt, rt):
        used[j] = 1
    lt = rt
else:
    for i in range(N):
        if P[i] != i:
            print(-1)
            break
    else:
        print('\n'.join(map(str, res)))

import sys
def main(N, P):
    I = [-1] * N
    for i, p in enumerate(P): I[p] = i
    p = 0
    s = 0
    ans = []
    while s < N:
        i = I[p]
        if s == i:
            p += 1
            s += 1
            continue
        for j in range(i, s, -1):
            ans.append(j)
        p += 1
        for j in range(s, i - 1):
            if P[j] != p:
                return None
            p += 1
        s = i
        p = s
        P[i] = P[i - 1]
        I[P[i]] = i
    if len(ans) != N - 1:
        return None
    return ans

def __starting_point():
    input = sys.stdin.readline
    N = int(input())
    *P, = [int(x) - 1 for x in input().split()]
    ans = main(N, P)
    if ans is None:
        print((-1))
    else:
        for a in ans:
            print(a)

__starting_point()

N = int(input())
P = list(map(int, input().split()))

P_idx = [0 for _ in range(N)]
for i in range(N):
    P_idx[P[i]-1] = i

ans = []
i = 0
while i < N:
    idx = P_idx[i]
    if i < idx:
        for j in range(idx-1, i-1, -1):
            P[j], P[j+1] = P[j+1], P[j]
            ans.append(j+1)
        i = idx
    else:
        i += 1

check = [i+1 for i in range(N)]
if P == check and len(ans) == N-1:
    for i in ans:
        print(i)
else:
    print((-1))


import sys

sys.setrecursionlimit(10 ** 6)
n = int(input())
p = list(map(int, input().split()))
pos = [0] * n
seen = [False] * n
ans = []
for i in range(n):
    p[i] -= 1
    pos[p[i]] = i

for i in range(n):
    if pos[i] == i:
        continue
    for j in range(pos[i], i, -1):
        if seen[j]:
            print(-1)
            return
        seen[j] = True
        p[j], p[j - 1] = p[j - 1], p[j]
        pos[p[j]], pos[p[j - 1]] = j, j - 1
        ans.append(j)
if len(ans) == n - 1:
    print(*ans, sep="\n")
else:
    print(-1)


import sys
input = sys.stdin.readline

N = int(input())
P = list(map(int, input().split()))
ans = []
tag = 1
prev = 0

for i in range(N):
    if P[i]==tag:
        for j in range(i-1, prev-1, -1):
            P[j], P[j+1] = P[j+1], P[j]
            ans.append(j+1)
        
        for j in range(prev, i):
            if P[j]!=j+1:
                print(-1)
                return
            
        tag = i+1
        prev = i
    
if len(ans)!=N-1:
    print(-1)
    return

for ans_i in ans:
    print(ans_i)

N = int(input())
A = list(map(int, input().split()))

p = []
for i in range(1, N + 1):
    p.append(i)

for i in range(N):
    if p[i] == A[i]:
        print((-1))
        return

index = 0
ans = []
for i in range(N):
    if A[i] == index + 1:
        for j in range(i - 1, index - 1, -1):
            A[j], A[j + 1] = A[j + 1], A[j]
            ans.append(j + 1)
        index = i

for i in range(len(A)):
    if i == len(A) - 1:
        break
    if A[i] + 1 == A[i + 1]:
        continue
    else:
        print((-1))
        return

for i in ans:
    print(i)


n = int(input())
p = list(map(int, input().split()))

ans, tmp, res = [], [], []
lst = [i + 1 for i in range(n)]
for i in range(n):
    if i != 0:
        tmp.append(i)
    if p[i] - 1 == len(ans):
        res += [p[i]] + p[len(ans):i - 1]
        ans += tmp[::-1]
        tmp = []
        p[i] = p[i - 1]
    if i == n - 1:
        res += [p[i]] + p[len(ans):i - 1]
        ans += tmp[::-1]
print(*(ans if res == lst else[-1]), sep='\n')


n = int(input())
l = list(map(int, input().split()))

l = [0] + l

pos = [0] * (n + 1)
for i in range(n + 1):
    pos[l[i]] = i

ans = []
flag = True
tmp = n
while tmp > 1:
    ind = pos[tmp]
    if ind < tmp:
        for i in range(ind + 1, tmp):
            if l[i + 1] != i:
                flag = False
                break
            l[i - 1], l[i] = l[i], l[i - 1]
            ans.append(i - 1)
        if flag:
            l[tmp - 1], l[tmp] = l[tmp], l[tmp - 1]
            ans.append(tmp - 1)
            tmp = ind
        else:
            break
    else:
        flag = False
        break

if flag:
    for ele in ans:
        print(ele)
else:
    print(-1)

import bisect,collections,copy,heapq,itertools,math,numpy,string,sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
P = [0]+LI()
ind = {i:0 for i in range(1,N)}
for i,p in enumerate(P[1:],1):
    ind[p] = i
ans = []
set_ans = set()
for i in range(1,N+1):
    if ind[i]==i:
        continue
    while 1:
        ind_i = ind[i]
        P[ind_i],P[ind_i-1] = P[ind_i-1],P[ind_i]
        ind[i] = ind_i-1
        ind[P[ind_i]] = ind_i
        if ind_i-1 in set_ans:
            print((-1))
            return
        ans.append(ind_i-1)
        set_ans.add(ind_i-1)
        if ind[i]==i:
            break
if len(ans)==N-1:
    for x in ans:
        print(x)
else:
    print((-1))


N = int(input())
P = list(map(int,input().split()))
search, before, count, flag, ans, pans = 1, 0, 0, 0, [], []
for i in range(N):
    x = P[i]
    if x == search:
        ans += pans[::-1]
        if i < N-1:
            if flag == 0:
                print(-1)
                return
            before, search, count, flag, pans = search, i+1, 0, 0, []
            P[i], x = P[i-1], P[i-1]
        
    if x != search:
        if flag == 1:
            print(-1)
            return
        if x > count+search+1:
            flag = 1
        pans.append(i+1)
        count += 1
        
print('\n'.join(map(str,ans)))

n = int(input())
p = list(map(int, input().split()))
swapped=[0] * (n-1)
noc=1

for now in range(0,n-1):
  if now>0 and swapped[now-1]==0:
    print(-1)
    return
  for i in range(now,n):
    if (p[i]-1==now):
      if(p[i]-1<i):
        for j in range(i-1,p[i]-2,-1):
          if swapped[j]!=0:
            print(-1)
            return
          p[j],p[j+1]=p[j+1],p[j]
          swapped[j]=noc  
          noc+=1
      break
if swapped[n-2]==0:
  print(-1)
  return
for i in range(0,n-1):
  print(swapped[i])

import copy
N = int(input())
Po = list(map(int,input().split()))
P = copy.deepcopy(Po)
pos = [0 for i in range(N+1)]
for i in range(N) :
    pos[P[i]] = i

i = 1
ans = []
while(i < N) :
    j = pos[i]
    if j<i : break
    for k in range(j,i-1,-1) :
        ans.append(k)
        P[k-1],P[k] = P[k],P[k-1]
    i = j+1
if(len(ans)==N-1 and P == [i+1 for i in range(N)]) :
    for out in ans :
        print(out)
else :
    print(-1)

N = int(input())
P_list = list(map(int, input().split()))

now = 1
pre = -1
ans = []
for i in range(N):
    if P_list[i] == now:
        for j in range(i-1, pre, -1):
            P_list[j], P_list[j+1] = P_list[j+1], P_list[j]
            ans.append(j+1)
        now = i+1
        pre = i-1

if P_list == sorted(P_list) and len(ans) == N-1:
        print(*ans, sep='\n')
else:
    print(-1)

n=int(input())
t=list(map(int,input().split()))
t=[-1]+t
pos=1
sol=[]
for i in range(1,n+1):
    if t[i]==pos:
        for j in range(i-1,pos-1,-1):
            sol.append(j)
            tmp=t[j]
            t[j]=t[j+1]
            t[j+1]=tmp
        pos=i      
for i in range(1,n+1):
    if t[i]!=i:
        print((-1))
        return
if len(sol)!=n-1:
    print((-1))
else:
    for i in sol:
        print(i)



n = int(input())
p = list(map(int, input().split()))

ans, tmp, res = [], [], []
lst = [i + 1 for i in range(n)]
for i in range(n):
    if i != 0:
        tmp.append(i)
    if p[i] - 1 == len(ans) or i == n - 1:
        res += [p[i]] + p[len(ans):i - 1]
        ans += tmp[::-1]
        tmp, p[i] = [], p[i - 1]
res += [p[i]]
print(*(ans if res == lst else[-1]), sep='\n')


import copy
N = int(input())
Po = list(map(int,input().split()))
P = copy.deepcopy(Po)
pos = [0 for i in range(N+1)]
for i in range(N) :
    pos[P[i]] = i+1

i = 1
ans = []
while(i < N) :
    j = pos[i]
    if j<=i : break
    for k in range(j-1,i-1,-1) :
        ans.append(k)
        P[k-1],P[k] = P[k],P[k-1]
    i = j
if(len(ans)==N-1 and P == [i+1 for i in range(N)]) :
    for out in ans :
        print(out)
else :
    print(-1)

n = int(input())
l = list(map(int, input().split()))

l = [0] + l

pos = [0] * (n + 1)
for i in range(n + 1):
    pos[l[i]] = i

ans = []
flag = True
tmp = n
while tmp > 1:
    ind = pos[tmp]
    if ind < tmp:
        for i in range(ind + 1, tmp):
            if l[i + 1] != i:
                flag = False
                break
            pos[l[i - 1]], pos[l[i]] = i, i - 1
            l[i - 1], l[i] = l[i], l[i - 1]
            ans.append(i - 1)
        if flag:
            pos[l[tmp - 1]], pos[l[tmp]] = tmp, tmp - 1
            l[tmp - 1], l[tmp] = l[tmp], l[tmp - 1]
            ans.append(tmp - 1)
            tmp = ind
        else:
            break
    else:
        flag = False
        break

if flag:
    for ele in ans:
        print(ele)
else:
    print(-1)

n=int(input())
p=list(map(int,input().split()))
ans=[]
kensa=set()
count=0
for i in range(1,n):
    j=i
    while j-1>=0 and  p[j-1]>p[j]:
        if j in kensa:
            print(-1)
            return
        ans.append(j)
        kensa.add(j)
        count+=1
        p[j-1],p[j]=p[j],p[j-1]
        j-=1
    if count>=n:
        print(-1)
        return
if len(ans)==n-1:
    for j in ans:
        print(j)
else:
    print(-1)

N = int(input())
P = list(map(int,input().split()))
search, before, count, flag, ans, pans = 1, 0, 0, 0, [], []
for i in range(N):
    x = P[i]
    if x == search:
        if i < N-1 and flag == 0:
            print(-1)
            return
        ans += pans[::-1]
        before, search, count, flag, pans = search, i+1, 0, 0, []
        P[i], x = P[i-1], P[i-1]
    if x != search:
        if flag == 1:
            print(-1)
            return
        if x == count+search+1:
            flag = 0
        if x > count+search+1:
            flag = 1
        pans.append(i+1)
        count += 1
    #print(i,x,pans)
print('\n'.join(map(str,ans)))

N=int(input())
P=list(map(int,input().split()))
ans=[]
l,r=0,0
for i in range(N):
  if P[i]==r+1:
    r=i
    for j in range(r,l,-1):
      P[j-1],P[j]=P[j],P[j-1]
      ans.append(j)
    l=r
  
if P!=sorted(P) or len(ans)!=N-1:
  print(-1);return
print(*ans,sep="\n")

N = int(input())
P = list(map(int, input().split()))

bef = 1
ans = []
for i in range(N):
    # find bef
    if P[i] == bef:
        for j in range(i, bef - 1, -1):
            # Move bef to it's postion with serial swapping from i to bef-1
            P[j], P[j-1] = P[j-1], P[j]
            ans.append(j)
        # update bef to min updatable position owner
        bef = i + 1

if len(ans) != (N-1) or P != sorted(P):
    # not using entire swap or unsorted without duplicate
    print('-1')
else:
    print('\n'.join(map(str, ans)))

N = int(input())
P_list = list(map(int, input().split()))

now = 1
pre = -1
ans = []
for i in range(N):
    if P_list[i] == now:
        for j in range(i-1, pre, -1):
            P_list[j], P_list[j+1] = P_list[j+1], P_list[j]
            ans.append(j+1)
        now = i+1
        pre = i-1

if P_list == sorted(P_list) and len(ans) == N-1:
        print(*ans, sep='\n')
else:
    print(-1)

n = int(input())
a = list(map(int, input().split()))
now=1
last_ind=0
lis=[]
ans=[]
for i in range(n):
    if a[i]==i+1:
        print("-1")
        return

def check(l):
    if len(l)==0:
        return False
    now=l[0]
    for i in range(1,len(l)-1):
        if l[i] < now:
            return False
        now=l[i]
    return True

for i in range(n):
    num=a[i]
    if num==now:
        if check(lis):
            cnt=0
            for j in range(i,last_ind,-1):
                ans.append(j)
                lis=[]
                cnt+=1
            last_ind=i
            now+=cnt
        else:
            print("-1")
            return
    lis.append(num)

if len(ans)!=n-1:
    print("-1")
    return

for i in range(n-1):
    print(ans[i])

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
P = LIST()

Q = [0]*N 
#Q[i]: iの場所
for i, p in enumerate(P):
	Q[p-1] = i

#print(Q)

check = [0]*N
ans = []

for i in range(N):
	p = Q[i]
	#print("#", i, p)
	if i < p:
		for j in range(p-1, i-1, -1):
			if check[j]:
				print(-1)
				return
			check[j] = 1
			ans.append(j+1)
			P[j], P[j+1] = P[j+1], P[j]
			Q[P[j]-1] -= 1
			Q[P[j+1]-1] += 1

for i in range(N-1, -1, -1):
	if i > p:
		for j in range(p, i):
			if check[j]:
				print(-1)
				return
			check[j] = 1
			ans.append(j+1)
			P[j], P[j+1] = P[j+1], P[j]
			Q[P[j]-1] -= 1
			Q[P[j+1]-1] += 1
			print(P, Q, ans)

if len(ans) < N-1:
	print(-1)
else:
	print(*ans, sep="\n")



n = int(input())
p = [int(x)-1 for x in input().split()]
ans, used = [],[False]*n
for i in range(n):
    while i > 0 and  p[i-1]>p[i]:
        if used[i]:
            print(-1)
            return
        else:
            used[i] = True
            p[i-1],p[i] = p[i],p[i-1]
            ans.append(i)
            i -= 1
if len(ans)==n-1:
    print(*ans,sep="\n")
else:
    print(-1)

def main():
  import sys
  input=sys.stdin.readline
  n=int(input())
  p=list(map(int,input().split()))
  c=[-1]*n
  for i in range(n):
    p[i]-=1
    c[p[i]]=i
  r=[False]*(n-1)
  ans=[]
  for i in range(n):
    j=c[i]
    while j!=i:
      if r[j-1]:
        print(-1)
        return
      ans.append(j)
      r[j-1]=True
      p[j-1],p[j]=p[j],p[j-1]
      c[p[j]]=j
      c[p[j-1]]=j-1
      j-=1
  for i in r:
    if not i:
      print(-1)
      return
  for i in ans:
    print(i)
main()

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
P = LIST()

Q = [0]*N 
for i, p in enumerate(P):
	Q[p-1] = i

check = [0]*N
ans = []

for i in range(N):
	p = Q[i]
	if i < p:
		for j in range(p-1, i-1, -1):
			if check[j]:
				print(-1)
				return
			check[j] = 1
			ans.append(j+1)
			P[j], P[j+1] = P[j+1], P[j]
			Q[P[j]-1] -= 1
			Q[P[j+1]-1] += 1

if len(ans) < N-1:
	print(-1)
else:
	print(*ans, sep="\n")



n=int(input())
p=list(map(int,input().split()))
now=1
ans=[]
for i in range(n):
    if p[i]==now:
        for j in range(i-1,now-2,-1):
            p[j],p[j+1]=p[j+1],p[j]
            ans.append(j+1)
        now=i+1
if p!=[i for i in range(1,n+1)] or len(ans)!=n-1:
    print(-1)
else:
    for i in ans:
        print(i)

N, *P = list(map(int,open(0).read().split()))
search, count, flag, ans, pans = 1, 0, 0, [], []
for i in range(N):
    x = P[i]
    if x == search:
        ans += pans[::-1]
        if i < N-1:
            if flag == 0:
                print(-1)
                return
            search, count, flag, pans = i+1, 0, 0, []
            P[i], x = P[i-1], P[i-1]
        
    if x != search:
        if flag == 1:
            print(-1)
            return
        if x > count+search+1:
            flag = 1
        pans.append(i+1)
        count += 1
        
print('\n'.join(map(str,ans)))

import numpy as np
n = int(input())
p = list(map(int, input().split()))
swapped=np.zeros((n-1,))
now=0
noc=1

for now in range(0,n-1):
  for i in range(now,n):
    if (p[i]-1==now):
      if(p[i]-1<i):
        for j in range(i-1,p[i]-2,-1):
          if swapped[j]!=0:
            print(-1)
            return
          kari=p[j]
          p[j]=p[j+1]
          p[j+1]=kari
          swapped[j]=noc  
          noc+=1
      break
for i in range(0,n-1):
  if int(swapped[i])==0:
    print(-1)
    return
for i in range(0,n-1):
  print(int(swapped[i])) 

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
#mod = 998244353
#from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N = INT()
P = LIST()

Q = [0]*N 
for i, p in enumerate(P):
	Q[p-1] = i

check = [0]*N
ans = []

for i in range(N):
	p = Q[i]
	if i < p:
		for j in range(p-1, i-1, -1):
			if check[j]:
				print(-1)
				return
			check[j] = 1
			ans.append(j+1)
			P[j], P[j+1] = P[j+1], P[j]
			Q[P[j]-1], Q[P[j+1]-1] = Q[P[j+1]-1], Q[P[j]-1]

if len(ans) < N-1:
	print(-1)
else:
	print(*ans, sep="\n")



import sys
input = sys.stdin.readline

N = int(input())
P = list(map(int, input().split()))
tage = 1
s = 0
ans = []

for i in range(N):
    if P[i]==tage:
        for j in range(i-1, s-1, -1):
            P[j], P[j+1] = P[j+1], P[j]
            ans.append(j)
        
        for j in range(s, i):
            if P[j]!=j+1:
                print(-1)
                return
        
        tage = i+1
        s = i

if len(ans)!=N-1:
    print(-1)
    return
    
for ans_i in ans:
    print(ans_i+1)

n = int(input())
p = list(map(int,input().split()))
p.insert(0,0)
t = [0] * (n+1)
for i in range(1,n+1):
    t[p[i]] = i
i = 1
f = 1
ans = []
while i < n:
    if p[i] != f:
        x = t[f]
        for j in range(i,x-1):
            if p[j] != j+1:
                print(-1)
                return
        for j in range(i,x)[::-1]:
            ans.append(j)
        p[x] = p[x-1]
        f = f+(x-i)
        i = x
    else:
        f += 1
        i += 1
if len(ans) != n-1:
    print(-1)
    return
for i in ans:
    print(i)

def int_1(n):
    return int(n)-1

N = int(input())
P = list(map(int_1,input().split()))

Number = [0]*N
for idx,p in enumerate(P):
    Number[p]=idx

ans =[]
target = 0
start = 0
while True:
    target_idx = Number[target]
    if target_idx <=start:
        print((-1))
        return
    for idx in range(target_idx-1,start-1,-1):
        P[idx+1],P[idx]=P[idx],P[idx+1]
        ans.append(idx)
    target = target_idx
    start = target_idx
    if start == N-1:
        break
for idx,p in enumerate(P):
    if p!=idx:
        print((-1))
        return
for an in ans:
    print((an+1))


n = int(input())
p = list(map(int, input().split()))

ans = []
left = 1
MIN = 1
while left < n:
    # 小さい数から順に確定していく
    # 移動前の位置より左はもう動かせない
    for i in range(left, n):
        if p[i] == MIN:
            # 確定した数が正しい位置にいるか
            for j in range(left-1, i-1):
                MIN = max(MIN, p[j])
                if p[j] != j+2:
                    print(-1)
                    return
            ans.extend(range(i,left-1,-1))
            p[i] = p[i-1]
            break
    else:
        print(-1)
        return
    left = i+1
    MIN += 1
print(*ans, sep='\n')

N=int(input())
P=list(map(int,input().split()))

dist=[0]*N
for i in range(N):
  dist[i]=i+1-P[i]

ans=[]
lp=1
for i in range(N-1):
    ch=0
    for j in range(lp-1,N-1):
      if dist[j]<0 and dist[j+1]>0:
        ans.append(j+1)
        dj=dist[j]
        dist[j]=dist[j+1]-1
        dist[j+1]=dj+1
        ch=1
        lp=j
        break
    if ch==0:
      print(-1)
      return

for i in dist:
  if i!=0:
    print(-1)
    return

for a in ans:
  print(a)

N = int(input())
P = list(map(int, input().split()))

ans = []
d = dict()
for i in range(N):
    d[P[i]] = i
num = 1
left = 0
s = set()
c = 0
while(num <= N):
    if num in s:
        if d[num] != num-1:
            print(-1)
            return
    elif d[num] != num-1:
        left = num - 1

        s.add(num)
        right = d[num]
        P[right] = P[right-1]
        d[P[right]] = right
        ans.append(right)
        d[num] = num-1
        for i in range(right-2, left-1, -1):
            s.add(P[i])
            d[P[i]] += 1
            ans.append(i+1)
    num += 1
if len(ans) == N-1:
    print(*ans, sep='\n')
else:
    print(-1)


def main():
  n=int(input())
  P=[int(x)-1 for x in input().split()]
  Q=[0]*n

  for i,p in enumerate(P):
    Q[p]=i

  L,i=[],n-1
  while i>0:
    if i==Q[i]:
      print((-1))
      return
    for j in range(Q[i],i):
      P[j],P[j+1]=P[j+1],P[j]
      L.append(j+1)
    for j in range(Q[i]+1,i+1):
      if P[j]!=j:
        print((-1))
        return
    i=Q[i]

  for l in L:
    print(l)

main()


N = int(input())
P = list(map(int, input().split()))
ans = []

idx = [0]*(N+1)
for n in range(N):
    idx[P[n]] = n

i = 1
while i < N :
    right = idx[i]
    left = i-1

    if right == left: 
        i += 1
    elif right < left: 
        break
    else:
        for i in range(right, left, -1):
            P[i], P[i-1] = P[i-1], P[i]
            idx[P[i]], idx[P[i-1]] = idx[P[i-1]], idx[P[i]]
            ans.append(i)
        i += right - left

check = [n+1 for n in range(N)]
if P == check and len(ans) == N-1 :
    print(*ans, sep="\n")
else:
    print(-1)

N = int(input())
Plist = list(map(int,input().split()))
Place = [0]*(N+1)
maxP = max(Plist)
for i in range(N):
    p = Plist[i]
    Place[p] = i+1
Plist = [0]+Plist
ans = 0
Nset = []
Na = set()
for i in range(N):
    maxplace = Place[maxP]
    while maxplace != maxP:
        if maxplace not in Na:
            Place[maxP] += 1
            a = Plist[maxplace+1]
            Place[a] -= 1
            Plist[maxplace] = a
            Plist[maxplace+1] = maxP
            Nset.append(maxplace)
            Na.add(maxplace)
            maxplace += 1
        else:
            ans = -1
            break
    maxP -= 1
if ans == -1:
    print(ans)
else:
    if len(Nset) == N-1:
        for n in Nset:
            print(n)
    else:
        print(-1)

import sys
 
input = sys.stdin.readline
N = int(input())
P = list(map(int, input().split()))
 
target = 1
ans = []
for i in range(N):
    if P[i] == target:
        for j in range(i, target-1, -1):
            P[j], P[j-1] = P[j-1], P[j]
            ans.append(j)
    
        target = i+1
        # print("i", i, "target", target)
    
# print(P)
if len(ans) != N-1:
    print(-1)
    return
for i in range(N):
    if P[i] != i+1:
        print(-1)
        return
 
print(*ans, sep="\n")