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: MEDIUM_HARD

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
	i += 1
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)
	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(-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
if len(ans) != n - 1:
	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(-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()))
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)
	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)
		elif 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)
		elif i + 1 in can:
			can.remove(i + 1)
			can_not.add(i + 1)
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(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')


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 = []
yn = ''
for i in range(n):
	if 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])
			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])
			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()))
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]))


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([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]
	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
	idx += 1
if ok and len(record) == N - 1:
	for ans in record:
		print(ans)
else:
	print(-1)


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 = 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))


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:

	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):
		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):
		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().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())
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()))
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 = []
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()))
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):
	if P[i] == bef:
		for j in range(i, bef - 1, -1):
			(P[j], P[j - 1]) = (P[j - 1], P[j])
			ans.append(j)
		bef = i + 1
if len(ans) != N - 1 or P != sorted(P):
	print('-1')
else:
	print('\n'.join(map(str, ans)))


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
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
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)


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 = 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)
elif len(Nset) == N - 1:
	for n in Nset:
		print(n)
else:
	print(-1)