You are given a permutation $p$ of integers from $1$ to $n$, where $n$ is an even number. 

Your goal is to sort the permutation. To do so, you can perform zero or more operations of the following type:   take two indices $i$ and $j$ such that $2 \cdot |i - j| \geq n$ and swap $p_i$ and $p_j$. 

There is no need to minimize the number of operations, however you should use no more than $5 \cdot n$ operations. One can show that it is always possible to do that.


-----Input-----

The first line contains a single integer $n$ ($2 \leq n \leq 3 \cdot 10^5$, $n$ is even) — the length of the permutation. 

The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the given permutation.


-----Output-----

On the first line print $m$ ($0 \le m \le 5 \cdot n$) — the number of swaps to perform.

Each of the following $m$ lines should contain integers $a_i, b_i$ ($1 \le a_i, b_i \le n$, $|a_i - b_i| \ge \frac{n}{2}$) — the indices that should be swapped in the corresponding swap.

Note that there is no need to minimize the number of operations. We can show that an answer always exists.


-----Examples-----
Input
2
2 1

Output
1
1 2
Input
4
3 4 1 2

Output
4
1 4
1 4
1 3
2 4

Input
6
2 5 3 1 4 6

Output
3
1 5
2 5
1 4



-----Note-----

In the first example, when one swap elements on positions $1$ and $2$, the array becomes sorted.

In the second example, pay attention that there is no need to minimize number of swaps.

In the third example, after swapping elements on positions $1$ and $5$ the array becomes: $[4, 5, 3, 1, 2, 6]$. After swapping elements on positions $2$ and $5$ the array becomes $[4, 2, 3, 1, 5, 6]$ and finally after swapping elements on positions $1$ and $4$ the array becomes sorted: $[1, 2, 3, 4, 5, 6]$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Sorting

Constructive algorithms


Solutions:
from sys import stdin, stdout
import bisect

def main():
	n = int(stdin.readline())
	arr = [int(el) for el in stdin.readline().split()]
	i = 0
	res = []
	while i < n:
		if arr[i] - 1 == i:
			i += 1
		else:
			pos2 = arr[i] - 1
			if abs(pos2 - i) >= n // 2:
				res.append([min(i + 1, pos2 + 1), max(i + 1, pos2 + 1)])
				temp = arr[i]
				arr[i] = arr[pos2]
				arr[pos2] = temp
			elif i < n // 2 and pos2 < n // 2:
				res.append([i + 1, n])
				res.append([pos2 + 1, n])
				res.append([i + 1, n])
				temp = arr[i]
				arr[i] = arr[pos2]
				arr[pos2] = temp
			elif i < n // 2 and pos2 >= n // 2:
				res.append([i + 1, n])
				res.append([1, pos2 + 1])
				res.append([1, n])
				res.append([1, pos2 + 1])
				res.append([i + 1, n])
				temp = arr[i]
				arr[i] = arr[pos2]
				arr[pos2] = temp
			else:
				res.append([1, i + 1])
				res.append([1, pos2 + 1])
				res.append([1, i + 1])
				temp = arr[i]
				arr[i] = arr[pos2]
				arr[pos2] = temp
	print(len(res))
	for i in range(len(res)):
		print(*res[i])
main()


input()
p = [int(x) - 1 for x in input().split()]
pos = [0] * len(p)
for (i, x) in enumerate(p):
	pos[x] = i
ans = []
for (i, x) in enumerate(p):
	if i == x:
		continue
	i_pos = pos[i]
	if 2 * abs(i_pos - i) < len(p):
		if 2 * i_pos >= len(p) and 2 * i >= len(p):
			ans.append((0, i_pos))
			ans.append((0, i))
			ans.append((0, i_pos))
		elif 2 * (len(p) - 1 - i_pos) >= len(p) and 2 * (len(p) - 1 - i) >= len(p):
			ans.append((len(p) - 1, i_pos))
			ans.append((len(p) - 1, i))
			ans.append((len(p) - 1, i_pos))
		else:
			fi = min(i_pos, i)
			la = max(i_pos, i)
			ans.append((fi, len(p) - 1))
			ans.append((0, len(p) - 1))
			ans.append((0, la))
			ans.append((0, len(p) - 1))
			ans.append((fi, len(p) - 1))
	else:
		ans.append((i, i_pos))
	(p[i_pos], p[i]) = (p[i], p[i_pos])
	(pos[p[i_pos]], pos[p[i]]) = (pos[p[i]], pos[p[i_pos]])
print(len(ans))
for (a, b) in ans:
	print(a + 1, b + 1)
assert sorted(p) == p


n = int(input())
a = [0] + list(map(int, input().split()))
cnt = 0
res = []

def swap(i: int, j: int):
	(a[i], a[j]) = (a[j], a[i])
pos = [0] * (n + 1)
for i in range(1, n + 1):
	pos[a[i]] = i
for i in range(1, n + 1):
	p = pos[i]
	if p == i:
		continue
	elif abs(p - i) * 2 >= n:
		swap(i, p)
		cnt += 1
		res.append((i, p))
	elif (i - 1) * 2 >= n:
		swap(i, p)
		cnt += 3
		res.extend([(1, i), (1, p), (1, i)])
	elif (p - 1) * 2 < n:
		swap(i, p)
		cnt += 3
		res.extend([(p, n), (i, n), (p, n)])
	else:
		swap(i, p)
		cnt += 5
		res.extend([(i, n), (1, p), (1, n), (i, n), (1, p)])
	pos[a[p]] = p
print(cnt)
print('\n'.join((str(i) + ' ' + str(j) for (i, j) in res)))


def fastio():
	import sys
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from collections import defaultdict as dd, Counter as C
from bisect import bisect_left as bl
(n,) = I()
a = [i - 1 for i in I()]
ans = []
pos = [0] * n
for i in range(n):
	pos[a[i]] = i
mid = n // 2

def swap(i, j):
	(x, y) = (a[i], a[j])
	(a[j], a[i]) = (x, y)
	(pos[x], pos[y]) = (j, i)
	ans.append([i + 1, j + 1])
if n % 2:
	if pos[mid] > mid:
		swap(0, pos[mid])
		swap(0, mid)
	else:
		swap(n - 1, pos[mid])
		swap(n - 1, mid)
	mid += 1
for i in range(1, n // 2):
	if pos[i] <= mid:
		swap(pos[i], n - 1)
	else:
		swap(pos[i], 0)
		swap(0, n - 1)
	swap(pos[i], i)
	if pos[mid + i - 1] >= mid:
		swap(pos[mid + i - 1], 0)
	else:
		swap(n - 1, pos[mid + i - 1])
		swap(n - 1, 0)
	swap(pos[mid + i - 1], mid + i - 1)
if a[0] != 0:
	swap(0, pos[0])
print(len(ans))
for i in ans:
	print(*i)


n = int(input())
perm = [int(t) for t in input().split(' ')]
idx = {n: i for (i, n) in enumerate(perm)}
ridx = {i: n for (i, n) in enumerate(perm)}
swaps = []
for i in range(n):
	desired = i + 1
	didx = idx[desired]
	if didx == i:
		ridx_ = dict()
	elif abs(i - didx) * 2 >= n:
		swaps.append((i, didx))
		ridx_ = {i: desired, didx: ridx[i]}
	else:
		if didx < n // 2:
			inter = n - 1
		else:
			inter = 0
		if abs(i - inter) * 2 >= n:
			swaps.append((didx, inter))
			swaps.append((i, inter))
		else:
			inter2 = 0 if inter == n - 1 else n - 1
			swaps.append((didx, inter))
			swaps.append((inter, inter2))
			swaps.append((i, inter2))
			swaps.append((inter2, inter))
		ridx_ = {i: desired, inter: ridx[i], didx: ridx[inter]}
	for (k, v) in ridx_.items():
		ridx[k] = v
		idx[v] = k
print(len(swaps))
print('\n'.join(['{} {}'.format(swap[0] + 1, swap[1] + 1) for swap in swaps]))


import os
import sys
from math import *
from collections import *
from bisect import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcdefghijklmnopqrstuvwxyz'
M = 998244353
EPS = 1e-06

def Ceil(a, b):
	return a // b + int(a % b > 0)

def value():
	return tuple(map(int, input().split()))

def array():
	return [int(i) for i in input().split()]

def Int():
	return int(input())

def Str():
	return input()

def arrayS():
	return [i for i in input().split()]

def swap(i, j):
	(ind[arr[i - 1]], ind[arr[j - 1]]) = (ind[arr[j - 1]], ind[arr[i - 1]])
	(arr[j - 1], arr[i - 1]) = (arr[i - 1], arr[j - 1])
	steps.append((i, j))
n = Int()
arr = array()
ind = {arr[i]: i + 1 for i in range(n)}
steps = []
for a in range(1, n):
	b = ind[a]
	if b == a:
		continue
	(a, b) = sorted((a, b))
	if b - a >= n // 2:
		swap(a, b)
	elif b <= n // 2:
		swap(a, n)
		swap(b, n)
		swap(a, n)
	elif a > n // 2:
		swap(a, 1)
		swap(b, 1)
		swap(a, 1)
	else:
		swap(1, b)
		swap(n, a)
		swap(1, n)
		swap(1, b)
		swap(n, a)
print(len(steps))
for i in steps:
	print(*i)


from collections import defaultdict
import sys

def input():
	return sys.stdin.readline().rstrip()

def slv():
	n = int(input())
	a = list(map(int, input().split()))
	res = []
	d = defaultdict(int)
	for (i, v) in enumerate(a):
		d[v] = i

	def swapR(V):
		idx_V = d[V]
		assert a[idx_V] == V
		if idx_V == V - 1:
			return
		if idx_V + 1 > n // 2:
			res.append((idx_V + 1, 1))
			exv = a[0]
			d[exv] = idx_V
			d[V] = 0
			(a[idx_V], a[0]) = (a[0], a[idx_V])
			swapR(V)
			return
		elif idx_V == 0:
			res.append((V, 1))
			exv = a[V - 1]
			d[V] = V - 1
			d[exv] = 0
			(a[0], a[V - 1]) = (a[V - 1], a[0])
			return
		else:
			exv = a[n - 1]
			res.append((n, idx_V + 1))
			d[exv] = idx_V
			d[V] = n - 1
			(a[idx_V], a[n - 1]) = (a[n - 1], a[idx_V])
			swapR(V)
			return

	def swapL(V):
		idx = d[V]
		assert a[idx] == V
		if V == 1:
			if all((a[i] == i + 1 for i in range(n))):
				return
		if idx != n - 1:
			exv = a[n - 1]
			res.append((idx + 1, n))
			d[V] = n - 1
			d[exv] = idx
			(a[idx], a[n - 1]) = (a[n - 1], a[idx])
		if V == 1:
			if all((a[i] == i + 1 for i in range(n))):
				return
		exv = a[V - 1]
		res.append((V, n))
		d[V] = V - 1
		d[exv] = n - 1
		(a[V - 1], a[n - 1]) = (a[n - 1], a[V - 1])
		return
	for i in range(n // 2 + 1, n):
		swapR(i)
	for i in range(n // 2, 0, -1):
		swapL(i)
	assert all((a[i] == i + 1 for i in range(n)))
	print(len(res))
	for (u, v) in res:
		print(u, v)
	return

def main():
	t = 1
	for i in range(t):
		slv()
	return
main()


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
l = [*map(int, input().split())]
l = [i - 1 for i in l]
pos = {}
ans = []
for (i, j) in enumerate(l):
	pos[j] = i

def swap(i, j):
	ans.append((pos[l[i]] + 1, pos[l[j]] + 1))
	(pos[l[i]], pos[l[j]]) = (pos[l[j]], pos[l[i]])
	(l[i], l[j]) = (l[j], l[i])

def solve(i):
	u = n - 1 if pos[i] < n // 2 else 0
	v = 0 if pos[i] < n // 2 else n - 1
	swap(pos[i], u)
	if abs(u - i) * 2 >= n:
		swap(u, i)
	else:
		swap(u, v)
		swap(v, i)
for i in range(1, n - 1):
	if l[i] != i:
		solve(i)
if l[0] != 0:
	swap(0, n - 1)
print(len(ans))
print('\n'.join([' '.join(map(str, [*i])) for i in ans]))


n = int(input())
(a, b) = ([], [0] * n)
for (i, e) in enumerate(input().split()):
	a.append(int(e))
	b[int(e) - 1] = i
(qu, ans) = ([], 0)
for i in range(n):
	if a[i] == i + 1:
		continue
	j = b[i]
	if j - i >= n // 2:
		qu.append((i + 1, j + 1))
		ans += 1
	elif j - i < n // 2 and j + 1 <= n // 2:
		qu.append((j + 1, n))
		qu.append((i + 1, n))
		qu.append((j + 1, n))
		ans += 3
	elif j - i < n // 2 and i + 1 > n // 2:
		qu.append((j + 1, 1))
		qu.append((i + 1, 1))
		qu.append((j + 1, 1))
		ans += 3
	else:
		qu.append((i + 1, n))
		qu.append((1, n))
		qu.append((1, j + 1))
		qu.append((1, n))
		qu.append((i + 1, n))
		ans += 5
	(b[i], b[a[i] - 1]) = (b[a[i] - 1], b[i])
	(a[i], a[j]) = (a[j], a[i])
print(ans)
print('\n'.join([' '.join(map(str, [*i])) for i in qu]))


n = int(input())
l = list([int(s) - 1 for s in input().split()])
pos = [0] * n
for (i, x) in enumerate(l):
	pos[x] = i
ans = []

def swap(i, j):
	(l[i], l[j]) = (l[j], l[i])
	(pos[l[i]], pos[l[j]]) = (pos[l[j]], pos[l[i]])
	ans.append((i + 1, j + 1))
for i in range(n // 2 - 1, -1, -1):
	p = pos[i]
	if p >= n // 2:
		swap(pos[i], 0)
		swap(0, n // 2 + i)
	else:
		swap(pos[i], n // 2 + i)
	swap(n // 2 + i, i)
	p = pos[n // 2 + i]
	if p < n // 2:
		swap(pos[n // 2 + i], n // 2 + i)
	else:
		swap(pos[n // 2 + i], 0)
		swap(0, n // 2 + i)
print(len(ans))
for (a, b) in ans:
	print(a, b)


import sys
input = sys.stdin.readline
n = int(input())
p = [-1] + list(map(int, input().split()))
l = [-1 for _ in range(n + 1)]
for i in range(1, n + 1):
	l[p[i]] = i
cnt = 0
ans = []
for i in range(2, n):
	if p[i] == i:
		pass
	else:
		c = l[i]
		if c <= n // 2 and i <= n // 2:
			ans.append((c, n))
			ans.append((i, n))
			cnt += 2
			(l[p[c]], l[p[n]]) = (l[p[n]], l[p[c]])
			(p[c], p[n]) = (p[n], p[c])
			(l[p[i]], l[p[n]]) = (l[p[n]], l[p[i]])
			(p[i], p[n]) = (p[n], p[i])
		elif c <= n // 2 and i > n // 2:
			ans.append((c, n))
			ans.append((1, n))
			ans.append((1, i))
			cnt += 3
			(l[p[c]], l[p[n]]) = (l[p[n]], l[p[c]])
			(p[c], p[n]) = (p[n], p[c])
			(l[p[1]], l[p[n]]) = (l[p[n]], l[p[1]])
			(p[1], p[n]) = (p[n], p[1])
			(l[p[1]], l[p[i]]) = (l[p[i]], l[p[1]])
			(p[1], p[i]) = (p[i], p[1])
		elif c > n // 2 and i <= n // 2:
			ans.append((1, c))
			ans.append((1, n))
			ans.append((i, n))
			cnt += 3
			(l[p[1]], l[p[c]]) = (l[p[c]], l[p[1]])
			(p[1], p[c]) = (p[c], p[1])
			(l[p[1]], l[p[n]]) = (l[p[n]], l[p[1]])
			(p[1], p[n]) = (p[n], p[1])
			(l[p[i]], l[p[n]]) = (l[p[n]], l[p[i]])
			(p[i], p[n]) = (p[n], p[i])
		else:
			ans.append((1, c))
			ans.append((1, i))
			cnt += 2
			(l[p[1]], l[p[c]]) = (l[p[c]], l[p[1]])
			(p[1], p[c]) = (p[c], p[1])
			(l[p[1]], l[p[i]]) = (l[p[i]], l[p[1]])
			(p[1], p[i]) = (p[i], p[1])
if p[1] == 1:
	pass
else:
	ans.append((1, n))
	cnt += 1
print(cnt)
for (a, b) in ans:
	print(a, b)


n = int(input())
p = [*map(int, input().split())]
p = [i - 1 for i in p]
pos = {}
ans = []
for (i, j) in enumerate(p):
	pos[j] = i

def swap(i, j):
	ans.append((pos[p[i]] + 1, pos[p[j]] + 1))
	(pos[p[i]], pos[p[j]]) = (pos[p[j]], pos[p[i]])
	(p[i], p[j]) = (p[j], p[i])

def do(i):
	u = n - 1 if pos[i] < n // 2 else 0
	v = 0 if pos[i] < n // 2 else n - 1
	swap(pos[i], u)
	if abs(u - i) * 2 >= n:
		swap(u, i)
	else:
		swap(u, v)
		swap(v, i)
for i in range(1, n - 1):
	if p[i] != i:
		do(i)
if p[0] != 0:
	swap(0, n - 1)
print(len(ans))
print('\n'.join([' '.join(map(str, [*i])) for i in ans]))


from collections import Counter, OrderedDict
from itertools import permutations as perm
from collections import deque
from sys import stdin
from bisect import *
from heapq import *
import math

def g():
	return stdin.readline().strip()

def gl():
	return g().split()

def gil():
	return [int(var) for var in gl()]

def gfl():
	return [float(var) for var in gl()]

def gcl():
	return list(g())

def gbs():
	return [int(var) for var in g()]
mod = int(1000000000.0) + 7
inf = float('inf')
(n,) = gil()
a = gil()
idx = [0] * n

def swap(i, j):
	(vi, vj) = (a[i], a[j])
	(idx[vi], idx[vj]) = (j, i)
	(a[i], a[j]) = (vj, vi)
	ans.append((i + 1, j + 1))
for i in range(n):
	a[i] -= 1
	idx[a[i]] = i
mid = (n - 1) // 2
ans = []
half = n // 2
for i in range(mid + 1):
	j = mid - i
	if a[j] != j:
		if abs(idx[j] - j) >= half:
			swap(idx[j], j)
		elif abs(idx[j] - (n - 1)) >= half:
			swap(idx[j], n - 1)
			swap(j, n - 1)
		else:
			swap(idx[j], 0)
			swap(idx[j], n - 1)
			swap(j, n - 1)
	j = mid + 1 + i
	if a[j] != j:
		if abs(idx[j] - j) >= half:
			swap(idx[j], j)
		elif idx[j] >= half:
			swap(idx[j], 0)
			swap(idx[j], j)
		else:
			swap(idx[j], n - 1)
			swap(0, n - 1)
			swap(0, j)
print(len(ans))
for r in ans:
	print(*r)


n = int(input())
a = list(map(int, input().split()))
a.insert(0, 12222)
p = (n + 1) * [0]
ret = 0
moves = []

def check(gg, ez):
	return 2 * abs(gg - ez) >= n

def where_go(i):
	if check(i, n):
		return n
	return 1

def swap(i, j):
	tmp1 = a[i]
	tmp2 = a[j]
	(a[i], a[j]) = (a[j], a[i])
	(p[tmp1], p[tmp2]) = (p[tmp2], p[tmp1])
	moves.append((i, j))
for (index, val) in enumerate(a):
	if index == 0:
		continue
	p[val] = index
for i in range(2, n):
	if check(i, p[i]):
		swap(i, p[i])
	else:
		swap(where_go(p[i]), p[i])
		if check(i, p[i]):
			swap(i, p[i])
		else:
			swap(where_go(p[i]), p[i])
			swap(i, p[i])
if p[1] == n:
	swap(1, n)
print(len(moves))
for (s1, s2) in moves:
	print(s1, s2)


import sys
n = int(input())
a = list(map(int, sys.stdin.readline().split()))
mark = [0 for x in range(n + 1)]
idex = 0
ans = []
for i in range(n):
	mark[a[i]] = i + 1
a = [0] + a

def swap(idex, changeNum):
	ans.append([str(mark[idex]), str(mark[changeNum])])
	myIdex = mark[idex]
	changeIdex = mark[changeNum]
	mark[idex] = mark[changeNum]
	mark[changeNum] = myIdex
	a[myIdex] = changeNum
	a[changeIdex] = idex
for i in range(1, n + 1):
	mem = 0
	while 1:
		if i != mark[i]:
			if abs(mark[i] - i) * 2 >= n:
				swap(i, a[i])
				break
			elif abs(mark[i] - 1) * 2 >= n:
				swap(i, a[1])
				mem = 1
			else:
				swap(i, a[n])
		else:
			break
	if mem:
		swap(1, a[1])
sys.stdout.write(str(len(ans)) + '\n')
for (c1, c2) in ans:
	sys.stdout.write(c1 + ' ' + c2 + '\n')


n = int(input())
li = list(map(int, input().split()))
pos = [0 for i in range(n + 1)]
for i in range(n):
	pos[li[i]] = i
ans = []
co = 0
for i in range(n):
	if li[i] != i + 1:
		k = pos[i + 1]
		if 2 * abs(k - i) >= n:
			co += 1
			ans.append([i + 1, k + 1])
			pos[i + 1] = i
			li[k] = li[i]
			li[i] = i + 1
			pos[li[k]] = k
		elif 2 * abs(k - n + 1) >= n and 2 * abs(i - n + 1) >= n:
			co += 3
			ans.append([n, k + 1])
			ans.append([n, i + 1])
			ans.append([n, k + 1])
			pos[i + 1] = i
			li[k] = li[i]
			li[i] = i + 1
			pos[li[k]] = k
		elif 2 * abs(k) >= n and 2 * abs(i) >= n:
			co += 3
			ans.append([1, k + 1])
			ans.append([1, i + 1])
			ans.append([1, k + 1])
			pos[i + 1] = i
			li[k] = li[i]
			li[i] = i + 1
			pos[li[k]] = k
		else:
			if k <= n // 2 - 1:
				ak = n
				ai = 1
			else:
				ai = n
				ak = 1
			co += 5
			ans.append([i + 1, ai])
			ans.append([ai, ak])
			ans.append([ak, k + 1])
			ans.append([ai, ak])
			ans.append([i + 1, ai])
			pos[i + 1] = i
			li[k] = li[i]
			li[i] = i + 1
			pos[li[k]] = k
print(co)
for i in ans:
	print(*i)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools
import random
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI():
	return [list(map(int, l.split())) for l in sys.stdin.readlines()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def pe(s):
	return print(str(s), file=sys.stderr)

def main():
	n = I()
	a = LI_()
	d = {}
	for i in range(n):
		d[a[i]] = i
	r = []

	def sw(t, u):
		c = a[t]
		e = a[u]
		d[c] = u
		d[e] = t
		a[t] = e
		a[u] = c
		r.append('{} {}'.format(t + 1, u + 1))
	n2 = n // 2
	for i in range(1, n - 1):
		if a[i] == i:
			continue
		t = d[i]
		u = a[i]
		if abs(t - i) < n2:
			p = 0
			if abs(t - p) < n2:
				p = n - 1
			sw(t, p)
			if abs(p - i) < n2:
				p = n - 1 - p
				sw(0, n - 1)
			sw(i, p)
		else:
			sw(t, i)
	if a[0] != 0:
		sw(0, n - 1)
	return '{}\n{}'.format(len(r), '\n'.join(r))
print(main())


import sys
n = int(input())
a = [int(_) - 1 for _ in sys.stdin.readline().split()]
b = [0 for _ in a]
for (id, v) in enumerate(a):
	b[v] = id
ans = []
for i in range(n):
	pos = b[i]
	target = i
	old_v = a[target]
	if pos == target:
		continue
	b[old_v] = pos
	b[i] = i
	a[target] = i
	a[pos] = old_v
	if abs(pos - target) * 2 >= n:
		ans.append((pos, target))
		continue
	elif max(pos, target) < n // 2:
		helper = n - 1
		ans.append((pos, helper))
		ans.append((target, helper))
		ans.append((pos, helper))
	elif min(pos, target) >= n // 2:
		helper = 0
		ans.append((pos, helper))
		ans.append((target, helper))
		ans.append((pos, helper))
	else:
		L = 0
		R = n - 1
		if pos > target:
			(pos, target) = (target, pos)
		ans.append((pos, R))
		ans.append((L, R))
		ans.append((L, target))
		ans.append((L, R))
		ans.append((pos, R))
print(len(ans))
print('\n'.join((f'{i[0] + 1} {i[1] + 1}' for i in ans)))


n = int(input())
b = list(map(int, input().split()))
d = dict()
r = n // 2
for j in range(n):
	d[b[j]] = j + 1
j = 1
c = []
while j <= n:
	if d[j] != j:
		k = d[j]
		if k - j >= r:
			c.append([k, j])
			d[b[j - 1]] = k
			d[j] = j
			(b[j - 1], b[k - 1]) = (b[k - 1], b[j - 1])
		elif n - j >= r:
			if n - k >= r:
				c.append([n, k])
				c.append([n, j])
				d[j] = j
				d[b[n - 1]] = k
				d[b[j - 1]] = n
				(b[k - 1], b[n - 1]) = (b[n - 1], b[k - 1])
				(b[j - 1], b[n - 1]) = (b[n - 1], b[j - 1])
			else:
				c.append([1, k])
				c.append([1, n])
				c.append([n, j])
				c.append([1, k])
				d[j] = j
				d[b[n - 1]] = k
				d[b[j - 1]] = n
				(b[k - 1], b[n - 1]) = (b[n - 1], b[k - 1])
				(b[j - 1], b[n - 1]) = (b[n - 1], b[j - 1])
		else:
			c.append([1, k])
			c.append([1, j])
			c.append([1, k])
			d[j] = j
			d[b[j - 1]] = k
			(b[j - 1], b[k - 1]) = (b[k - 1], b[j - 1])
	j += 1
print(len(c))
for j in c:
	print(*j)


n = int(input())
a = [int(x) for x in input().split()]
answer = []
index = [0] * (n + 1)
for i in range(n):
	index[a[i]] = i
for item in range(1, n + 1):
	i = index[item]
	if i > n - i - 1:
		answer.append((1, i + 1))
		(a[0], a[i]) = (a[i], a[0])
		index[a[0]] = 0
		index[a[i]] = i
		if item - 1 > n - item:
			answer.append((1, item))
			(a[0], a[item - 1]) = (a[item - 1], a[0])
			index[a[0]] = 0
			index[a[item - 1]] = item - 1
		else:
			answer.append((1, n))
			(a[0], a[-1]) = (a[-1], a[0])
			index[a[0]] = 0
			index[a[-1]] = n - 1
			answer.append((item, n))
			(a[item - 1], a[-1]) = (a[-1], a[item - 1])
			index[a[item - 1]] = item - 1
			index[a[-1]] = n - 1
	else:
		answer.append((i + 1, n))
		(a[i], a[-1]) = (a[-1], a[i])
		index[a[i]] = i
		index[a[-1]] = n - 1
		if item - 1 > n - item:
			answer.append((1, n))
			(a[0], a[-1]) = (a[-1], a[0])
			index[a[0]] = 0
			index[a[-1]] = n - 1
			answer.append((1, item))
			(a[0], a[item - 1]) = (a[item - 1], a[0])
			index[a[0]] = 0
			index[a[item - 1]] = item - 1
		else:
			answer.append((n, item))
			(a[-1], a[item - 1]) = (a[item - 1], a[-1])
			index[a[-1]] = n - 1
			index[a[item - 1]] = item - 1
x = len(answer)
print(x)
for i in range(x):
	print(*answer[i])


n = int(input())
a = [0] + list(map(int, input().split()))
d = {}
b = []
for i in range(1, n + 1):
	d[a[i]] = i
m = 0
for i in range(1, n + 1):
	ele = a[i]
	if ele != i and abs(i - d[i]) * 2 >= n:
		m += 1
		b.append([i, d[i]])
		a[i] = i
		a[d[i]] = ele
		d[ele] = d[i]
		d[i] = i
	elif ele != i and abs(i - d[i]) * 2 < n and (i <= n // 2) and (2 * (d[i] - 1) >= n):
		m += 5
		b.append([1, d[i]])
		b.append([1, n])
		b.append([i, n])
		b.append([1, n])
		b.append([1, d[i]])
		a[i] = i
		a[d[i]] = ele
		d[ele] = d[i]
		d[i] = i
	elif ele != i and abs(i - d[i]) * 2 < n and (i <= n // 2) and (2 * (d[i] - 1) < n):
		m += 3
		b.append([n, d[i]])
		b.append([i, n])
		b.append([n, d[i]])
		a[i] = i
		a[d[i]] = ele
		d[ele] = d[i]
		d[i] = i
	elif ele != i and abs(i - d[i]) * 2 < n:
		m += 3
		b.append([1, d[i]])
		b.append([i, 1])
		b.append([1, d[i]])
		a[i] = i
		a[d[i]] = ele
		d[ele] = d[i]
		d[i] = i
print(m)
for i in b:
	print(*i)


import sys, math

def read_int():
	return int(sys.stdin.readline().strip())

def read_int_list():
	return list(map(int, sys.stdin.readline().strip().split()))

def read_string():
	return sys.stdin.readline().strip()

def read_string_list(delim=' '):
	return sys.stdin.readline().strip().split(delim)

def swap(this_index, true_index):
	global pos, arr, outs
	pos[arr[this_index]] = true_index
	pos[arr[true_index]] = this_index
	(arr[this_index], arr[true_index]) = (arr[true_index], arr[this_index])
	outs.append((this_index + 1, true_index + 1))
	if abs(true_index - this_index) < limit:
		print('fuck!')
n = read_int()
arr = read_int_list()
outs = []
limit = n // 2
pos = {}
for i in range(n):
	pos[arr[i]] = i
i = 0
while i < n:
	if arr[i] != i + 1:
		true_index = pos[i + 1]
		this_index = i
		if abs(true_index - this_index) >= limit:
			swap(this_index, true_index)
		elif this_index < n // 2 and true_index < n // 2:
			sentinal = n - 1
			swap(true_index, sentinal)
			swap(this_index, sentinal)
			swap(sentinal, true_index)
		elif this_index >= n // 2 and true_index >= n // 2:
			sentinal = 0
			swap(true_index, sentinal)
			swap(this_index, sentinal)
			swap(sentinal, true_index)
		else:
			(sentinal_1, sentinal_2) = (0, n - 1)
			(first, second) = (min(this_index, true_index), max(this_index, true_index))
			swap(first, sentinal_2)
			swap(second, sentinal_1)
			swap(sentinal_1, sentinal_2)
			swap(sentinal_1, second)
			swap(sentinal_2, first)
	i += 1
print(len(outs))
for t in outs:
	print(t[0], t[1])


import os
import sys
from io import BytesIO, IOBase
from collections import Counter
import math as mt
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)
mod = int(1000000000.0) + 7

def power(k, n):
	if n == 0:
		return 1
	if n % 2:
		return power(k, n - 1) * k % mod
	t = power(k, n // 2)
	return t * t % mod

def totalPrimeFactors(n):
	count = 0
	if n % 2 == 0:
		count += 1
		while n % 2 == 0:
			n //= 2
	i = 3
	while i * i <= n:
		if n % i == 0:
			count += 1
			while n % i == 0:
				n //= i
		i += 2
	if n > 2:
		count += 1
	return count

def main():
	n = int(input())
	P = list(map(int, input().split()))
	for i in range(n):
		P[i] -= 1
	where = [0] * n
	for i in range(n):
		where[P[i]] = i
	Z = []

	def swapper(ind1, ind2):
		if ind1 > ind2:
			(ind1, ind2) = (ind2, ind1)
		swaps = []
		left = 0
		right = n - 1
		if ind1 != left and 2 * abs(ind2 - left) >= n:
			swaps.append((ind2, left))
			ind2 = left
		if ind2 != right and 2 * abs(ind1 - right) >= n:
			swaps.append((ind1, right))
			ind1 = right
		if ind1 != left and 2 * abs(ind2 - left) >= n:
			swaps.append((ind2, left))
			ind2 = left
		assert 2 * abs(ind1 - ind2) >= n
		swaps.append((ind1, ind2))
		swaps += swaps[:-1][::-1]
		assert len(swaps) & 1
		for (l, r) in swaps:
			(where[P[r]], where[P[l]], P[l], P[r]) = (l, r, P[r], P[l])
			Z.append((l, r))
	for p in reversed(range(n)):
		indx = where[p]
		indy = p
		if indx == indy:
			continue
		swapper(indx, indy)
	print(len(Z))
	print('\n'.join((str(x + 1) + ' ' + str(y + 1) for (x, y) in Z)))
	return
main()


n = int(input()) // 2
array = [int(i) for i in input().split()]
pos = [0] * (2 * n + 1)
for i in range(2 * n):
	pos[array[i]] = i
printl = []

def swap(a, b):
	printl.append(str(a + 1) + ' ' + str(b + 1))
	temp = array[a]
	array[a] = array[b]
	array[b] = temp
	pos[array[b]] = b
	pos[array[a]] = a
for i in range(n):
	if array[i] != i + 1:
		q = pos[i + 1]
		if q >= i + n:
			swap(q, i)
		elif q >= n:
			swap(0, q)
			swap(0, 2 * n - 1)
			swap(2 * n - 1, i)
			swap(q, 0)
		else:
			swap(q, 2 * n - 1)
			swap(2 * n - 1, i)
for i in range(n, 2 * n):
	if array[i] != i + 1:
		if array[0] != i + 1:
			swap(0, pos[i + 1])
		swap(0, i)
print(len(printl))
[print(i) for i in printl]


def swap(i, j):
	global ans, elind, indel
	ans.append((i, j))
	x = indel[i]
	y = indel[j]
	elind[x] = j
	elind[y] = i
	indel[i] = y
	indel[j] = x
n = int(input())
elind = [0] * (n + 1)
indel = [0] * (n + 1)
i = 1
for el in map(int, input().split()):
	elind[el] = i
	indel[i] = el
	i += 1
ans = []
t = n // 2
if elind[1] - 1 < t and elind[1] != 1:
	swap(elind[1], n)
	swap(n, 1)
elif elind[1] != 1:
	swap(elind[1], 1)
if n - elind[n] < t and elind[n] != n:
	pol = elind[n]
	swap(elind[n], 1)
	swap(1, n)
	swap(pol, 1)
elif elind[n] != n:
	swap(elind[n], n)
for i in range(2, n):
	pol = elind[i]
	if pol == i:
		continue
	elif abs(pol - i) < t:
		if pol - 1 >= t:
			swap(pol, 1)
			if i - 1 >= t:
				swap(1, i)
				swap(pol, 1)
			else:
				swap(1, n)
				swap(n, i)
				swap(1, n)
				swap(pol, 1)
		else:
			swap(pol, n)
			if n - i >= t:
				swap(n, i)
				swap(pol, n)
			else:
				swap(1, n)
				swap(1, i)
				swap(1, n)
				swap(pol, n)
	else:
		swap(pol, i)
assert len(ans) <= 5 * n
print(len(ans))
for el in ans:
	print(*el)


from sys import stdin
input = stdin.readline
n = int(input())
a = list(map(int, input().split()))
a = [0] + a
cnt = 0
res = []

def swap(i: int, j: int):
	(a[i], a[j]) = (a[j], a[i])
pos = [0] * (n + 1)
for i in range(1, n + 1):
	pos[a[i]] = i
for i in range(1, n + 1):
	p = pos[i]
	if p == i:
		continue
	elif abs(p - i) * 2 >= n:
		swap(i, p)
		cnt += 1
		res.append(f'{i} {p}')
	elif (i - 1) * 2 >= n:
		swap(i, p)
		cnt += 3
		res.extend([f'1 {i}', f'1 {p}', f'1 {i}'])
	elif (p - 1) * 2 < n:
		swap(i, p)
		cnt += 3
		res.extend([f'{p} {n}', f'{i} {n}', f'{p} {n}'])
	else:
		swap(i, p)
		cnt += 5
		res.extend([f'{i} {n}', f'{1} {p}', f'{1} {n}', f'{i} {n}', f'{1} {p}'])
	pos[a[p]] = p
print(cnt)
print('\n'.join(res))


n = int(input())
b = list(map(int, input().split()))
a = list(zip(b, range(n)))
a.sort()
a = dict(a)
swaps = []

def swap(i, j):
	if i == j:
		return []
	if 2 * abs(i - j) >= n:
		return [(i, j)]
	ans = []
	ii = i
	jj = j
	if i < n // 2:
		ans.append((i, n - 1))
		ii = n - 1
	if j >= n // 2:
		ans.append((j, 0))
		jj = 0
	ans.append((ii, jj))
	if i < n // 2:
		ans.append((i, n - 1))
	if j >= n // 2:
		ans.append((j, 0))
	return ans
ans = []
for i in range(n):
	ans.extend(swap(i, a[i + 1]))
	t = b[i]
	b[i] = b[a[i + 1]]
	b[a[i + 1]] = t
	a[t] = a[i + 1]
	a[i + 1] = i
print(len(ans))
for k in ans:
	print(k[0] + 1, k[1] + 1)


import os
import heapq
import sys
import math
import bisect
import operator
from collections import defaultdict
from io import BytesIO, IOBase

def gcd(a, b):
	if b == 0:
		return a
	else:
		return gcd(b, a % b)

def power(x, p, m):
	res = 1
	while p:
		if p & 1:
			res = res * x % m
		x = x * x % m
		p >>= 1
	return res

def inar():
	return [int(k) for k in input().split()]

def lcm(num1, num2):
	return num1 * num2 // gcd(num1, num2)

def binaryToDecimal(n):
	return int(n, 2)

def main():
	n = int(input())
	arr = [int(el) for el in input().split()]
	i = 0
	res = []
	while i < n:
		if arr[i] - 1 == i:
			i += 1
		else:
			pos2 = arr[i] - 1
			if abs(pos2 - i) >= n // 2:
				res.append([min(i + 1, pos2 + 1), max(i + 1, pos2 + 1)])
				temp = arr[i]
				arr[i] = arr[pos2]
				arr[pos2] = temp
			elif i < n // 2 and pos2 < n // 2:
				res.append([i + 1, n])
				res.append([pos2 + 1, n])
				res.append([i + 1, n])
				temp = arr[i]
				arr[i] = arr[pos2]
				arr[pos2] = temp
			elif i < n // 2 <= pos2:
				res.append([i + 1, n])
				res.append([1, pos2 + 1])
				res.append([1, n])
				res.append([1, pos2 + 1])
				res.append([i + 1, n])
				temp = arr[i]
				arr[i] = arr[pos2]
				arr[pos2] = temp
			else:
				res.append([1, i + 1])
				res.append([1, pos2 + 1])
				res.append([1, i + 1])
				temp = arr[i]
				arr[i] = arr[pos2]
				arr[pos2] = temp
	print(len(res))
	for i in range(len(res)):
		print(*res[i])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


n = int(input())
p = list(map(int, input().split()))
ps = p.copy()
ps.sort()
dp = dict()
ds = dict()
for i in range(n):
	if p[i] in dp:
		dp[p[i]] += [i]
	else:
		dp[p[i]] = [i]
		ds[p[i]] = 0
lop = []
for i in range(n):
	if p[i] != ps[i]:
		a = i
		b = dp[ps[i]][ds[ps[i]]]
		if abs(b - a) >= n // 2:
			lop.append([a + 1, b + 1])
		else:
			if a < n // 2 and b < n // 2:
				bl = [n]
			elif a >= n // 2 and b >= n // 2:
				bl = [1]
			elif a < n // 2:
				bl = [n, 1]
			else:
				bl = [1, n]
			if len(bl) == 2:
				lop.append([a + 1, bl[0]])
				lop.append([bl[0], bl[1]])
				lop.append([bl[1], b + 1])
				lop.append([bl[0], bl[1]])
				lop.append([a + 1, bl[0]])
			else:
				lop.append([a + 1, bl[0]])
				lop.append([b + 1, bl[0]])
				lop.append([a + 1, bl[0]])
		(p[a], p[b]) = (p[b], p[a])
		(dp[p[a]][ds[p[a]]], dp[p[b]][ds[p[b]]]) = (dp[p[b]][ds[p[b]]], dp[p[a]][ds[p[a]]])
	ds[p[i]] += 1
print(len(lop))
for op in lop:
	print(*op)


import sys
input = sys.stdin.readline
mii = lambda : map(int, input().split())
n = int(input())
p = list(mii())
for i in range(n):
	p[i] -= 1
ans = []
r1 = set(list(range(n)))
while r1:
	r2 = set()
	r1.add(0)
	r1.add(n - 1)
	for i in r1:
		if p[i] == i:
			continue
		if p[i] == 0 or p[i] == n - 1:
			continue
		r2.add(i)
		if 2 * (i - 0) >= n:
			loc = 0
			ans.append((0, i))
			(p[0], p[i]) = (p[i], p[0])
		else:
			loc = n - 1
			ans.append((n - 1, i))
			(p[n - 1], p[i]) = (p[i], p[n - 1])
		if 2 * abs(p[loc] - loc) < n:
			loc = n - 1 - loc
			ans.append((0, n - 1))
			(p[n - 1], p[0]) = (p[0], p[n - 1])
		loc2 = p[loc]
		ans.append((loc, loc2))
		(p[loc], p[loc2]) = (p[loc2], p[loc])
	r1 = r2
if p[0] != 0:
	ans.append((0, n - 1))
	(p[n - 1], p[0]) = (p[0], p[n - 1])
assert p == sorted(p)
print(len(ans))
for (i, j) in ans:
	print('%d %d' % (i + 1, j + 1))


n = int(input())
p = list(map(int, input().split()))
index = [None] * (n + 1)
for i in range(n):
	index[p[i]] = i
ret = []
for i in range(n):
	if p[i] == i + 1:
		continue
	target = index[i + 1]
	if abs(i - target) * 2 >= n:
		ret.append((i + 1, target + 1))
	elif i * 2 < n and target * 2 < n:
		ret.extend([(target + 1, n), (i + 1, n), (target + 1, n)])
	elif i * 2 >= n and target * 2 >= 2:
		ret.extend([(target + 1, 1), (i + 1, 1), (target + 1, 1)])
	elif target * 2 < n:
		ret.extend([(n, target + 1), (1, n), (i + 1, 1), (n, 1), (n, target + 1)])
	else:
		ret.extend([(1, target + 1), (1, n), (i + 1, n), (n, 1), (1, target + 1)])
	(p[i], p[target]) = (p[target], p[i])
	index[p[i]] = i
	index[p[target]] = target
print(len(ret))
print('\n'.join(('%d %d' % (swap[0], swap[1]) for swap in ret)))


def swap(a, b, position, array):
	x = array[a - 1]
	y = array[b - 1]
	(array[a - 1], array[b - 1]) = (y, x)
	(position[x], position[y]) = (position[y], position[x])
	return (position, array)

def diamond_swap(a, position, array):
	n = len(position)
	init = position[a]
	if a <= n // 2:
		if init < n // 2:
			pairs = [(init + 1, n), (a, n)]
		else:
			pairs = [(1, init + 1), (1, n), (a, n)]
	elif init < n // 2:
		pairs = [(init + 1, n), (1, n), (1, a)]
	else:
		pairs = [(1, init + 1), (1, a)]
	for p in pairs:
		k = swap(p[0], p[1], position, array)
		(position, array) = (k[0], k[1])
	return pairs

def solve():
	n = int(input())
	array = [int(x) for x in input().split()]
	position = dict()
	for i in range(n):
		position[array[i]] = i
	order = []
	for i in range(1, n // 2 + 1):
		order.append(i)
		order.append(n - i + 1)
	swaps = []
	while order:
		cur = order.pop()
		k = diamond_swap(cur, position, array)
		for p in k:
			swaps.append(p)
	print(len(swaps))
	for p in swaps:
		print(*p)
	return
solve()


n = int(input())
ps = list(map(int, input().split()))
res = []
i = 0
while i < n:
	j = ps[i] - 1
	if i == j:
		i += 1
		continue
	elif abs(i - j) >= n // 2:
		res.append((i + 1, j + 1))
		(ps[i], ps[j]) = (ps[j], ps[i])
	elif i + 1 <= n // 2 and j + 1 <= n // 2:
		res.append((i + 1, n - 1 + 1))
		res.append((j + 1, n - 1 + 1))
		res.append((i + 1, n - 1 + 1))
		(ps[i], ps[n - 1]) = (ps[n - 1], ps[i])
		(ps[j], ps[n - 1]) = (ps[n - 1], ps[j])
		(ps[i], ps[n - 1]) = (ps[n - 1], ps[i])
	elif i + 1 > n // 2 and j + 1 > n // 2:
		res.append((i + 1, 1))
		res.append((j + 1, 1))
		res.append((i + 1, 1))
		(ps[i], ps[0]) = (ps[0], ps[i])
		(ps[j], ps[0]) = (ps[0], ps[j])
		(ps[i], ps[0]) = (ps[0], ps[i])
	else:
		i1 = max(i, j)
		j1 = min(i, j)
		res.append((j1 + 1, n))
		(ps[j1], ps[n - 1]) = (ps[n - 1], ps[j1])
		res.append((i1 + 1, 1))
		(ps[i1], ps[0]) = (ps[0], ps[i1])
		res.append((1, n))
		(ps[0], ps[n - 1]) = (ps[n - 1], ps[0])
		res.append((j1 + 1, n))
		(ps[j1], ps[n - 1]) = (ps[n - 1], ps[j1])
		res.append((i1 + 1, 1))
		(ps[i1], ps[0]) = (ps[0], ps[i1])
print(len(res))
for (a, b) in res:
	print(a, b)


import sys
commands = []

def swap_x_y(array_, x, y):
	temp = array_[x - 1]
	array_[x - 1] = array_[y - 1]
	array_[y - 1] = temp

def mega_swap(array_, x):
	n = len(array_)
	h = n // 2 + 1
	y = array_[x - 1]
	first = 1
	last = 1
	if x < h:
		first = n
	if y < h:
		last = n
	commands.append(str(x) + ' ' + str(first))
	swap_x_y(array_, x, first)
	if first == y:
		return 0
	if first != last:
		commands.append(str(last) + ' ' + str(first))
		swap_x_y(array_, first, last)
	commands.append(str(y) + ' ' + str(last))
	swap_x_y(array_, last, y)

def count(array_):
	answ = 0
	for (i, x) in enumerate(array_[1:n - 1]):
		if i + 2 == x:
			answ += 1
	return answ
n = int(input())
seq = list(map(int, input().split(' ')))
for loop in range(2):
	ind = 0
	while ind < n:
		t = seq[ind]
		if t == ind + 1 or t == 1 or t == n:
			ind += 1
		else:
			mega_swap(seq, ind + 1)
if seq[0] != 1:
	mega_swap(seq, 1)
print(len(commands))
print(*commands, sep='\n')


from sys import stdin
n = int(stdin.readline().strip())
s = list(map(int, stdin.readline().strip().split()))
s1 = []
dic = dict()
for i in range(n):
	s1.append([s[i], i])
s1.sort()
for i in range(n):
	dic[s1[i][0]] = i
d = n // 2
ans = []
for i in range(n):
	if s1[i][1] == i:
		continue
	if 2 * abs(i - s1[i][1]) < n:
		if s1[i][1] < d:
			x = abs(n - 1 - s1[i][1])
			ans.append([s1[i][1] + 1, n])
			y = s[s1[i][1] + x]
			y1 = s1[i].copy()
			s[s1[i][1] + x] = s1[i][0]
			s[y1[1]] = y
			s1[i][1] += x
			s1[dic[y]][1] -= x
		elif i >= d:
			x = s1[i][1]
			x2 = s1[i][1]
			ans.append([1, x + 1])
			ans.append([1, i + 1])
			ans.append([1, x + 1])
			x1 = s[i]
			y = s[i]
			s[i] = s[x]
			s[x] = x1
			x = abs(i - x)
			s1[i][1] = i
			s1[dic[y]][1] = x2
		else:
			x = s1[i][1]
			x2 = s1[i][1]
			if x != n - 1:
				i1 = n - 1
			else:
				i1 = n - 2
			ans.append([1, x + 1])
			ans.append([1, i1 + 1])
			ans.append([1, x + 1])
			x1 = s[i1]
			y = s[i1]
			s[i1] = s[x]
			s[x] = x1
			x = abs(i1 - x)
			s1[i][1] = i1
			s1[dic[y]][1] = x2
	if s1[i][1] != i:
		x = abs(i - s1[i][1])
		y = s[s1[i][1] - x]
		y1 = s1[i].copy()
		s[s1[i][1] - x] = s1[i][0]
		s[y1[1]] = y
		s1[i][1] -= x
		s1[dic[y]][1] += x
		ans.append([i + 1, i + x + 1])
	if s1[i][1] != i:
		x = abs(i - s1[i][1])
		y = s[s1[i][1] - x]
		y1 = s1[i].copy()
		s[s1[i][1] - x] = s1[i][0]
		s[y1[1]] = y
		s1[i][1] -= x
		s1[dic[y]][1] += x
		ans.append([i + 1, i + x + 1])
print(len(ans))
for i in ans:
	print(*i)


def swap(index, swap_index, perm, indices, moves, cu):
	curr = perm[index - 1]
	temp = perm[swap_index - 1]
	perm[swap_index - 1] = curr
	perm[index - 1] = temp
	(indices[curr], indices[temp]) = (swap_index, index)
	moves.append((index, swap_index))

def main():
	n = int(input())
	perm = list(map(int, input().split()))
	indices = {}
	for i in range(1, n + 1):
		indices[perm[i - 1]] = i
	moves = []
	for i in range(n // 2):
		curr = i + 1
		if indices[curr] != i + 1:
			index = indices[curr]
			if index <= n // 2:
				swap(index, n, perm, indices, moves, curr)
				swap(i + 1, n, perm, indices, moves, curr)
			elif index != n:
				swap(index, 1, perm, indices, moves, curr)
				if curr > 1:
					swap(1, n, perm, indices, moves, curr)
					swap(i + 1, n, perm, indices, moves, curr)
					swap(index, 1, perm, indices, moves, curr)
			else:
				swap(index, 1, perm, indices, moves, curr)
				if curr > 1:
					swap(index, 1, perm, indices, moves, curr)
					swap(i + 1, n, perm, indices, moves, curr)
	for i in range(n // 2, n):
		curr = i + 1
		if indices[curr] != i + 1:
			index = indices[curr]
			if index >= n // 2:
				swap(index, 1, perm, indices, moves, curr)
				swap(i + 1, 1, perm, indices, moves, curr)
				swap(index, 1, perm, indices, moves, curr)
	print(len(moves))
	for i in moves:
		print(i[0], i[1])
main()


from sys import exit
N = int(input())
A = list(map(int, input().split()))
X = [0] + A
V = {v: i for (i, v) in enumerate(X[1:], 1)}

def swap(i, j):
	Ans.append((i, j))
	(V[X[i]], V[X[j]]) = (j, i)
	(X[i], X[j]) = (X[j], X[i])
Ans = []
k = N // 2
for i in range(k, 0, -1):
	v = V[i]
	if v != i:
		if 2 * abs(v - i) < N:
			if v >= k:
				swap(v, 1)
				swap(1, N)
			else:
				swap(v, N)
		v = V[i]
		swap(v, i)
	v = V[2 * k + 1 - i]
	if v != 2 * k + 1 - i:
		if 2 * abs(v - (2 * k + 1 - i)) < N:
			if v >= k:
				swap(v, 1)
			else:
				swap(v, N)
				swap(1, N)
		v = V[2 * k + 1 - i]
		swap(v, 2 * k + 1 - i)
print(len(Ans))
for a in Ans:
	print(*a)


n = int(input())
l = list(map(int, input().split()))
ll = [-1] * (n + 1)
for i in range(n):
	ll[l[i]] = i
res = []
for k in range(1, n + 1):
	i = k
	j = ll[k]
	if 2 * abs(j + 1 - i) >= n:
		res.append((i, j + 1))
		(l[i - 1], l[j]) = (l[j], l[i - 1])
		(ll[l[i - 1]], ll[l[j]]) = (ll[l[j]], ll[l[i - 1]])
	elif i != j + 1:
		if 2 * abs(j + 1 - n) >= n and 2 * abs(i - n) >= n:
			res.append((i, n))
			(l[i - 1], l[n - 1]) = (l[n - 1], l[i - 1])
			(ll[l[i - 1]], ll[l[n - 1]]) = (ll[l[n - 1]], ll[l[i - 1]])
			res.append((j + 1, n))
			(l[j], l[n - 1]) = (l[n - 1], l[j])
			(ll[l[j]], ll[l[n - 1]]) = (ll[l[n - 1]], ll[l[j]])
			res.append((i, n))
			(l[i - 1], l[n - 1]) = (l[n - 1], l[i - 1])
			(ll[l[i - 1]], ll[l[n - 1]]) = (ll[l[n - 1]], ll[l[i - 1]])
		elif 2 * abs(j + 1 - 1) >= n and 2 * abs(i - 1) >= n:
			res.append((i, 1))
			(l[i - 1], l[1 - 1]) = (l[1 - 1], l[i - 1])
			(ll[l[i - 1]], ll[l[1 - 1]]) = (ll[l[1 - 1]], ll[l[i - 1]])
			res.append((j + 1, 1))
			(l[j], l[1 - 1]) = (l[1 - 1], l[j])
			(ll[l[j]], ll[l[1 - 1]]) = (ll[l[1 - 1]], ll[l[j]])
			res.append((i, 1))
			(l[i - 1], l[1 - 1]) = (l[1 - 1], l[i - 1])
			(ll[l[i - 1]], ll[l[1 - 1]]) = (ll[l[1 - 1]], ll[l[i - 1]])
		else:
			if i > j + 1:
				(i, j) = (j + 1, i - 1)
			res.append((i, n))
			(l[i - 1], l[n - 1]) = (l[n - 1], l[i - 1])
			(ll[l[i - 1]], ll[l[n - 1]]) = (ll[l[n - 1]], ll[l[i - 1]])
			res.append((j + 1, 1))
			(l[j], l[1 - 1]) = (l[1 - 1], l[j])
			(ll[l[j]], ll[l[1 - 1]]) = (ll[l[1 - 1]], ll[l[j]])
			res.append((n, 1))
			(l[n - 1], l[1 - 1]) = (l[1 - 1], l[n - 1])
			(ll[l[n - 1]], ll[l[1 - 1]]) = (ll[l[1 - 1]], ll[l[n - 1]])
			res.append((i, n))
			(l[i - 1], l[n - 1]) = (l[n - 1], l[i - 1])
			(ll[l[i - 1]], ll[l[n - 1]]) = (ll[l[n - 1]], ll[l[i - 1]])
			res.append((j + 1, 1))
			(l[j], l[1 - 1]) = (l[1 - 1], l[j])
			(ll[l[j]], ll[l[1 - 1]]) = (ll[l[1 - 1]], ll[l[j]])
print(len(res))
for i in res:
	print(i[0], i[1])


import bisect
import decimal
from decimal import Decimal
import os
from collections import Counter
import bisect
from collections import defaultdict
import math
import random
import heapq
from math import sqrt
import sys
from functools import reduce, cmp_to_key
from collections import deque
import threading
from itertools import combinations
from io import BytesIO, IOBase
from itertools import accumulate
decimal.getcontext().prec = 46

def primeFactors(n):
	prime = set()
	while n % 2 == 0:
		prime.add(2)
		n = n // 2
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		while n % i == 0:
			prime.add(i)
			n = n // i
	if n > 2:
		prime.add(n)
	return list(prime)

def getFactors(n):
	factors = []
	i = 1
	while i <= math.sqrt(n):
		if n % i == 0:
			if n // i == i:
				factors.append(i)
			else:
				factors.append(i)
				factors.append(n // i)
		i = i + 1
	return factors

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	num = []
	for p in range(2, n + 1):
		if prime[p]:
			num.append(p)
	return num

def lcm(a, b):
	return a * b // math.gcd(a, b)

def sort_dict(key_value):
	return sorted(key_value.items(), key=lambda kv: (kv[1], kv[0]))

def list_input():
	return list(map(int, input().split()))

def num_input():
	return map(int, input().split())

def string_list():
	return list(input())

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def binaryToDecimal(n):
	return int(n, 2)

def DFS(n, s, adj):
	visited = [False for i in range(n + 1)]
	stack = []
	stack.append(s)
	while len(stack):
		s = stack[-1]
		stack.pop()
		if not visited[s]:
			visited[s] = True
		for node in adj[s]:
			if not visited[node]:
				stack.append(node)

def condition_satisfied(ans, position, arr, pos, wrong_num, right_num, i):
	ans.append((i + 1, pos + 1))
	position[wrong_num] = pos
	position[right_num] = i
	(arr[pos], arr[i]) = (wrong_num, right_num)
	return (ans, arr, position)

def solve():
	n = int(input())
	arr = list_input()
	position = {}
	ans = []
	for i in range(n):
		position[arr[i]] = i
	for i in range(n):
		if arr[i] == i + 1:
			continue
		pos = position[i + 1]
		(wrong_num, right_num) = (arr[i], i + 1)
		if abs(i - pos) >= n // 2:
			(ans, arr, position) = condition_satisfied(ans, position, arr, pos, wrong_num, right_num, i)
		elif abs(n - pos - 1) >= n // 2:
			ans.append((n, pos + 1))
			(position[right_num], position[arr[-1]]) = (n - 1, pos)
			(arr[pos], arr[-1]) = (arr[-1], arr[pos])
			pos = n - 1
			if abs(i - pos) >= n // 2:
				(ans, arr, position) = condition_satisfied(ans, position, arr, pos, wrong_num, right_num, i)
			else:
				ans.append((1, n))
				(position[right_num], position[arr[0]]) = (0, pos)
				(arr[0], arr[-1]) = (arr[-1], arr[0])
				pos = 0
				(ans, arr, position) = condition_satisfied(ans, position, arr, pos, wrong_num, right_num, i)
		else:
			ans.append((1, pos + 1))
			(position[right_num], position[arr[0]]) = (0, pos)
			(arr[0], arr[pos]) = (arr[pos], arr[0])
			pos = 0
			if abs(i - pos) >= n // 2:
				(ans, arr, position) = condition_satisfied(ans, position, arr, pos, wrong_num, right_num, i)
			else:
				ans.append((1, n))
				(position[right_num], position[arr[-1]]) = (n - 1, pos)
				(arr[0], arr[-1]) = (arr[-1], arr[0])
				pos = n - 1
				(ans, arr, position) = condition_satisfied(ans, position, arr, pos, wrong_num, right_num, i)
	print(len(ans))
	for (u, v) in ans:
		print(u, v)
t = 1
for _ in range(t):
	solve()


res = []
n = int(input())
a = [int(x) for x in input().strip().split()]
ind = [i for i in range(n)]
s_ind = [i[1] for i in sorted(zip(a, ind))]
m = n // 2
dic = {}
for i in range(n):
	dic[i] = i

def swap(a, b, dic):
	dic[ind[a]] = b
	dic[ind[b]] = a
	(ind[a], ind[b]) = (ind[b], ind[a])
	res.append((a + 1, b + 1))
	return dic
for i in range(n):
	dic[i] = i
for k in range(n):
	i = k
	u = s_ind[k]
	j = dic[u]
	if ind[i] == u:
		pass
	elif 2 * abs(i - j) >= n:
		dic = swap(i, j, dic)
	else:
		if i + m <= n - 1:
			e = i + m
		else:
			e = i - m
		if j + m <= n - 1:
			f = j + m
		else:
			f = j - m
		if 2 * abs(e - f) >= n:
			dic = swap(i, e, dic)
			dic = swap(f, j, dic)
			dic = swap(e, f, dic)
			dic = swap(f, j, dic)
			dic = swap(i, e, dic)
		elif 2 * abs(e - j) >= n:
			swap(j, e, dic)
			swap(i, e, dic)
			swap(j, e, dic)
		else:
			swap(j, f, dic)
			swap(i, f, dic)
			swap(j, f, dic)
print(len(res))
for r in res:
	print(r[0], r[1])


n = int(input())
p = list(map(int, input().split()))
p = [guy - 1 for guy in p]
locs = [0] * n
for i in range(n):
	locs[p[i]] = i
out = []
for j in range(n // 2):
	if locs[j] < n // 2 and locs[j] != j:
		out.append((n, locs[j] + 1))
		(a, b) = (locs[j], p[-1])
		(p[a], p[-1], locs[j], locs[b]) = (b, j, n - 1, a)
		out.append((n, j + 1))
		a = p[j]
		(p[n - 1], p[j], locs[j], locs[a]) = (a, j, j, n - 1)
	elif locs[j] != j:
		out.append((j + 1, locs[j] + 1))
		(a, b) = (p[j], locs[j])
		(p[j], p[b], locs[j], locs[a]) = (j, a, j, b)
	if locs[j + n // 2] >= n // 2 and locs[j + n // 2] != j + n // 2:
		out.append((locs[j + n // 2] + 1, 1))
		out.append((1, j + n // 2 + 1))
		out.append((locs[j + n // 2] + 1, 1))
		(a, b) = (p[j + n // 2], locs[j + n // 2])
		(p[j + n // 2], p[b], locs[j + n // 2], locs[a]) = (j + n // 2, a, j + n // 2, b)
	elif locs[j + n // 2] != j + n // 2:
		out.append((locs[j + n // 2] + 1, n))
		out.append((n, 1))
		out.append((1, j + n // 2 + 1))
		out.append((n, 1))
		out.append((locs[j + n // 2] + 1, n))
		(a, b) = (p[j + n // 2], locs[j + n // 2])
		(p[j + n // 2], p[b], locs[j + n // 2], locs[a]) = (j + n // 2, a, j + n // 2, b)
print(len(out))
for guy in out:
	print(guy[0], guy[1])


N = int(input())
M = N // 2
A = [int(a) - 1 for a in input().split()]
B = [0] * N
ANS = []
for i in range(N):
	B[A[i]] = i

def calc(i):
	j = B[i]
	if j == i:
		return 0
	if abs(j - i) >= M:
		ANS.append(str(i + 1) + ' ' + str(j + 1))
	elif i < M and j < M:
		ANS.append(str(i + 1) + ' ' + str(N))
		ANS.append(str(j + 1) + ' ' + str(N))
		ANS.append(str(i + 1) + ' ' + str(N))
	elif i >= M and j >= M:
		ANS.append(str(1) + ' ' + str(i + 1))
		ANS.append(str(1) + ' ' + str(j + 1))
		ANS.append(str(1) + ' ' + str(i + 1))
	elif i < M:
		ANS.append(str(i + 1) + ' ' + str(N))
		ANS.append(str(1) + ' ' + str(N))
		ANS.append(str(1) + ' ' + str(j + 1))
		ANS.append(str(1) + ' ' + str(N))
		ANS.append(str(i + 1) + ' ' + str(N))
	else:
		ANS.append(str(j + 1) + ' ' + str(N))
		ANS.append(str(1) + ' ' + str(N))
		ANS.append(str(1) + ' ' + str(i + 1))
		ANS.append(str(1) + ' ' + str(N))
		ANS.append(str(j + 1) + ' ' + str(N))
	m = A[i]
	(A[i], A[B[i]]) = (i, A[i])
	B[m] = B[i]
	B[i] = i
for i in range(N):
	calc(i)
print(len(ANS))
print('\n'.join(ANS))


import sys
import math
from collections import defaultdict

def swap(i, j, dic, ans, nums):
	dic[nums[i]] = j
	dic[nums[j]] = i
	(nums[i], nums[j]) = (nums[j], nums[i])
	ans.append([i, j])
n = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
dic = defaultdict(int)
nums = [0 for _ in range(n)]
for i in range(n):
	dic[arr[i]] = i
	nums[i] = arr[i]
arr.sort()
ans = []
(l, r) = (n // 2 - 1, n // 2)
while l >= 0:
	if dic[arr[l]] == l:
		l -= 1
	else:
		cur = dic[arr[l]]
		if (n - cur - 1) * 2 >= n:
			swap(n - 1, cur, dic, ans, nums)
			swap(l, n - 1, dic, ans, nums)
		else:
			swap(0, cur, dic, ans, nums)
			swap(0, n - 1, dic, ans, nums)
			swap(l, n - 1, dic, ans, nums)
		l -= 1
	if dic[arr[r]] == r:
		r += 1
	else:
		cur = dic[arr[r]]
		if (n - cur - 1) * 2 >= n:
			swap(cur, n - 1, dic, ans, nums)
			swap(0, n - 1, dic, ans, nums)
			swap(0, r, dic, ans, nums)
		else:
			swap(0, cur, dic, ans, nums)
			swap(0, r, dic, ans, nums)
		r += 1
print(len(ans))
for i in range(len(ans)):
	print(ans[i][0] + 1, ans[i][1] + 1)


n = int(input())
A = list(map(int, input().split()))
Swaps = []

def swap(i, j):
	if i >= n // 2 and j < n // 2:
		swap_in_both_parts(j, i)
	elif j >= n // 2 and i < n // 2:
		swap_in_both_parts(i, j)
	elif j < n // 2 and i < n // 2:
		swap_in_left_part(i, j)
	elif j >= n // 2 and i >= n // 2:
		swap_in_right_part(i, j)
	else:
		print('Whattt?????')

def swap_in_left_part(f, s):
	Swaps.append((f, n - 1))
	Swaps.append((s, n - 1))
	Swaps.append((f, n - 1))
	(A[f], A[s]) = (A[s], A[f])

def swap_in_right_part(f, s):
	Swaps.append((0, f))
	Swaps.append((0, s))
	Swaps.append((0, f))
	(A[f], A[s]) = (A[s], A[f])

def swap_in_both_parts(f, s):
	if f == 0 or s == n - 1:
		Swaps.append((f, s))
	else:
		Swaps.append((0, s))
		Swaps.append((f, n - 1))
		Swaps.append((0, n - 1))
		Swaps.append((0, s))
		Swaps.append((f, n - 1))
	(A[f], A[s]) = (A[s], A[f])
i = 0
while i != n:
	if i != A[i] - 1:
		(st, fin) = (i, A[i] - 1)
		swap(st, fin)
	else:
		i += 1
print(len(Swaps))
for i in range(len(Swaps)):
	print(Swaps[i][0] + 1, Swaps[i][1] + 1)


n = int(input())
p = [i for i in map(int, input().split())]
actions = []

def swap(i, j):
	(p[i - 1], p[j - 1]) = (p[j - 1], p[i - 1])
	actions.append(f'{i} {j}')

def print_(p):
	print('\t'.join(map(str, p)))
i = 0
while i < n:
	ind = i + 1
	v = p[i]
	distance = abs(ind - v)
	if ind == v:
		i += 1
	elif 2 * distance >= n:
		swap(ind, v)
	elif ind <= n / 2 and v <= n / 2:
		pivot = n
		swap(ind, pivot)
		swap(v, pivot)
		swap(ind, pivot)
	elif ind > n / 2 and v >= n / 2:
		pivot = 1
		swap(ind, pivot)
		swap(v, pivot)
		swap(ind, pivot)
	else:
		left = min(ind, v)
		right = max(ind, v)
		l_piv = 1
		r_piv = n
		swap(left, r_piv)
		swap(right, l_piv)
		swap(r_piv, l_piv)
		swap(left, r_piv)
		swap(right, l_piv)
print(len(actions))
print('\n'.join(actions))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inara():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inp()
a = inara()
pos = [0] * n
for i in range(n):
	a[i] -= 1
	pos[a[i]] = i
ans = []

def solve(i, j):
	(pos[a[i]], pos[a[j]]) = (pos[a[j]], pos[a[i]])
	(a[i], a[j]) = (a[j], a[i])
	ans.append([i + 1, j + 1])
for i in range(n):
	if i == pos[i]:
		continue
	if 2 * (pos[i] - i) >= n:
		solve(i, pos[i])
	elif 2 * pos[i] >= n:
		if i * 2 >= n:
			x = pos[i]
			solve(0, x)
			solve(0, i)
			solve(0, x)
		else:
			x = pos[i]
			solve(0, x)
			solve(0, n - 1)
			solve(i, n - 1)
			solve(0, x)
	else:
		solve(pos[i], n - 1)
		solve(i, n - 1)
print(len(ans))
for swap in ans:
	print(*swap)


def exchange(curr, next):
	global ans
	store_indx_next = indx[curr]
	store_indx_curr = indx[arr[next]]
	store_arr = arr[next]
	(arr[next], arr[indx[curr]]) = (curr, arr[next])
	(indx[store_arr], indx[curr]) = (store_indx_next, store_indx_curr)
	ans.append([store_indx_next, store_indx_curr])
n = int(input())
arr = [0] + list(map(int, input().split()))
indx = [0 for i in range(n + 1)]
for i in range(1, n + 1):
	indx[arr[i]] = i
ans = []
for i in range(1, n // 2 + 1):
	if indx[n // 2 + i] > n // 2:
		exchange(n // 2 + i, i)
		exchange(n // 2 + i, n // 2 + i)
	else:
		exchange(n // 2 + i, n)
		exchange(n // 2 + i, i)
		exchange(n // 2 + i, n // 2 + i)
	if indx[i] > n // 2:
		exchange(i, i)
	else:
		exchange(i, n)
		exchange(i, i)
print(len(ans))
for i in ans:
	print(i[0], i[1])


n = int(input())
a = [int(q) - 1 for q in input().split()]
s = [0] * n
for q in range(n):
	s[a[q]] = q
ans = []
for q in range(n):
	(w, w1, w2) = (s[q], a[q], a[n - 1])
	w3 = a[w]
	if q == w:
		continue
	elif abs(q - w) * 2 >= n:
		ans.append(sorted([q, w]))
		(s[q], s[w1], a[q], a[w]) = (q, w, w3, w1)
	elif q >= n // 2:
		ans.append([0, w])
		ans.append([0, q])
		ans.append([0, w])
		(s[q], s[w1], a[q], a[w]) = (q, w, w3, w1)
	elif w < n // 2:
		ans.append([w, n - 1])
		ans.append([q, n - 1])
		ans.append([w, n - 1])
		(s[q], s[w1], a[q], a[w]) = (q, w, w3, w1)
	else:
		ans.append([0, w])
		ans.append([0, n - 1])
		ans.append([q, n - 1])
		ans.append([0, w])
		(a[q], a[n - 1], a[w], s[q], s[w2], s[w1]) = (q, w1, w2, q, w, n - 1)
print(len(ans))
for q in ans:
	print(q[0] + 1, q[1] + 1)


r = int
d = input
N = map
R = enumerate
x = abs
J = range
L = print
h = len
a = str
n = r(d())
l = [*N(r, d().split())]
l = [i - 1 for i in l]
X = {}
q = []
for (i, j) in R(l):
	X[j] = i

def y(i, j):
	q.append((X[l[i]] + 1, X[l[j]] + 1))
	(X[l[i]], X[l[j]]) = (X[l[j]], X[l[i]])
	(l[i], l[j]) = (l[j], l[i])

def Q(i):
	u = n - 1 if X[i] < n // 2 else 0
	v = 0 if X[i] < n // 2 else n - 1
	y(X[i], u)
	if x(u - i) * 2 >= n:
		y(u, i)
	else:
		y(u, v)
		y(v, i)
for i in J(1, n - 1):
	if l[i] != i:
		Q(i)
if l[0] != 0:
	y(0, n - 1)
L(h(q))
L('\n'.join([' '.join(N(a, [*i])) for i in q]))


from sys import stdin

def input():
	return stdin.readline().strip()
n = int(input())
count = 0
swaps = []

def exchange(i, j):
	global a
	global ind
	global count
	count += 1
	swaps.append((i + 1, j + 1))
	(a[i], a[j]) = (a[j], a[i])
	ind[a[i] - 1] = i
	ind[a[j] - 1] = j
a = list(map(int, input().split()))
ind = [0] * n
for i in range(n):
	ind[a[i] - 1] = i
for i in range(n):
	x = ind[i]
	if x == i:
		continue
	if abs(x - i) >= n // 2:
		exchange(x, i)
	elif (x < n // 2) ^ (i < n // 2):
		if x < n // 2:
			beg = n - 1
			end = 0
		else:
			beg = 0
			end = n - 1
		exchange(beg, x)
		exchange(beg, end)
		exchange(end, i)
		exchange(beg, x)
	elif x < n // 2:
		exchange(x, n - 1)
		exchange(i, n - 1)
		exchange(x, n - 1)
	else:
		exchange(x, 0)
		exchange(i, 0)
		exchange(x, 0)
print(count)
for i in swaps:
	print(*i)


n = int(input())
arr = list(map(int, input().split()))
ansarr = []
dict1 = {}
dict2 = {}
for i in range(n):
	dict1[arr[i]] = i + 1
	dict2[i + 1] = arr[i]
j = n // 2 + 1
for i in range(n // 2, 1, -1):
	if dict1[i] != i:
		if dict1[i] > n // 2:
			element = dict2[1]
			val = dict1[i]
			ansarr.append(1)
			ansarr.append(dict1[i])
			dict1[i] = 1
			dict2[1] = i
			dict1[element] = val
			dict2[val] = element
			element = dict2[n]
			val = dict1[i]
			ansarr.append(n)
			ansarr.append(dict1[i])
			dict1[i] = n
			dict2[n] = i
			dict1[element] = val
			dict2[val] = element
			element = dict2[i]
			val = dict1[i]
			ansarr.append(i)
			ansarr.append(dict1[i])
			dict1[i] = i
			dict2[i] = i
			dict1[element] = val
			dict2[val] = element
		elif dict1[i] < n // 2 + 1:
			element = dict2[n]
			val = dict1[i]
			ansarr.append(n)
			ansarr.append(dict1[i])
			dict1[i] = n
			dict2[n] = i
			dict1[element] = val
			dict2[val] = element
			element = dict2[i]
			val = dict1[i]
			ansarr.append(i)
			ansarr.append(dict1[i])
			dict1[i] = i
			dict2[i] = i
			dict1[element] = val
			dict2[val] = element
	if dict1[j] != j:
		if dict1[j] > n // 2:
			element = dict2[1]
			val = dict1[j]
			ansarr.append(1)
			ansarr.append(dict1[j])
			dict1[j] = 1
			dict2[1] = j
			dict1[element] = val
			dict2[val] = element
			element = dict2[j]
			val = dict1[j]
			ansarr.append(j)
			ansarr.append(dict1[j])
			dict1[j] = j
			dict2[j] = j
			dict1[element] = val
			dict2[val] = element
		else:
			element = dict2[n]
			val = dict1[j]
			ansarr.append(n)
			ansarr.append(dict1[j])
			dict1[j] = n
			dict2[n] = j
			dict1[element] = val
			dict2[val] = element
			element = dict2[1]
			val = dict1[j]
			ansarr.append(1)
			ansarr.append(dict1[j])
			dict1[j] = 1
			dict2[1] = j
			dict1[element] = val
			dict2[val] = element
			element = dict2[j]
			val = dict1[j]
			ansarr.append(j)
			ansarr.append(dict1[j])
			dict1[j] = j
			dict2[j] = j
			dict1[element] = val
			dict2[val] = element
	j += 1
if dict1[1] != 1:
	ansarr.append(1)
	ansarr.append(n)
print(len(ansarr) // 2)
print(*ansarr)


n = int(input())
n2 = n // 2
p = list(map(int, input().split()))
d = [0] * n
for (i, v) in enumerate(p):
	d[v - 1] = i
r = []

def sw(i, j):
	r.append((i + 1, j + 1))

def swap(i, j):
	if i == j:
		pass
	elif abs(i - j) >= n2:
		sw(i, j)
		p[j] = p[i]
	else:
		ti = n - 1 if i < n2 else 0
		tj = n - 1 if j < n2 else 0
		sw(i, ti)
		if ti != tj:
			sw(ti, tj)
		sw(tj, j)
		if ti != tj:
			sw(ti, tj)
		sw(i, ti)
		p[j] = p[i]
for (i, v) in enumerate(p):
	j = d[i]
	swap(i, j)
	d[v - 1] = j
print(len(r))
print('\n'.join((f'{a} {b}' for (a, b) in r)))


import sys, os
f = lambda : list(map(int, input().split()))
if 'local' in os.environ:
	sys.stdin = open('./input.txt', 'r')
ans = []
n = 0
p = []

def swap(x, y):
	global ans, p
	if abs(x - y) >= n // 2:
		ans.append((x, y))
		(p[x], p[y]) = (p[y], p[x])
	elif abs(x - (n - 1)) >= n // 2:
		swap(x, n - 1)
		swap(y, n - 1)
	else:
		swap(x, 0)
		swap(y, 0)

def solve():
	global n, p, ans
	n = f()[0]
	p = f()
	for i in range(n):
		if p[i] == i + 1:
			continue
		else:
			while p[i] != i + 1:
				swap(i, p[i] - 1)
	print(len(ans))
	for i in ans:
		print(i[0] + 1, i[1] + 1)
solve()


def change(a, b):
	global p, antip, ans
	antip[p[a]] = b
	antip[p[b]] = a
	(p[a], p[b]) = (p[b], p[a])
	ans.append((a, b))

def place(k):
	global p, antip
	i = antip[k]
	if i <= n // 2 and k <= n // 2:
		change(i, n)
		change(k, n)
	elif i <= n // 2 and k > n // 2:
		change(i, n)
		change(1, n)
		change(1, k)
	elif i > n // 2 and k <= n // 2:
		change(i, 1)
		change(1, n)
		change(n, k)
	elif i > n // 2 and k > n // 2:
		change(i, 1)
		change(1, k)
n = int(input())
p = list(map(int, input().split()))
p = [None] + p
antip = [None] * (n + 1)
ans = []
for i in range(1, len(p)):
	antip[p[i]] = i
for i in range(n // 2):
	t = 2 * i + 1
	k = (n + 1 + t) // 2
	place(k)
	k = (n + 1 - t) // 2
	place(k)
print(len(ans))
for i in ans:
	print(*i)


from sys import stdin, stdout
n = int(stdin.readline())
l = [0] + list(map(int, stdin.readline().split()))
pos = [0] * (n + 1)
for i in range(1, n + 1):
	pos[l[i]] = i
ans = []

def change(i):
	global ans, n, l, pos
	if pos[i] <= n // 2:
		y = l[n]
		x = pos[i]
		(l[pos[i]], l[n]) = (l[n], l[pos[i]])
		pos[y] = x
		pos[i] = n
		ans.append(str(x) + ' ' + str(n))
	else:
		y = l[1]
		x = pos[i]
		(l[1], l[pos[i]]) = (l[pos[i]], l[1])
		pos[y] = x
		pos[i] = 1
		ans.append('1 ' + str(x))
for i in range(2, n):
	if i <= n / 2:
		while l[n] != i:
			change(i)
		pos[l[i]] = n
		pos[i] = i
		l[n] = l[i]
		l[i] = i
		ans.append(str(i) + ' ' + str(n))
	else:
		while l[1] != i:
			change(i)
		pos[l[i]] = 1
		pos[i] = i
		l[1] = l[i]
		l[i] = i
		ans.append('1 ' + str(i))
if l[1] != 1:
	ans.append('1 ' + str(n))
stdout.write(str(len(ans)) + '\n')
for i in ans:
	stdout.write(i + '\n')