There are n coins labeled from 1 to n. Initially, coin c_i is on position i and is facing upwards ((c_1, c_2, ..., c_n) is a permutation of numbers from 1 to n). You can do some operations on these coins. 

In one operation, you can do the following:

  * Choose 2 distinct indices i and j.

  * Then, swap the coins on positions i and j.

  * Then, flip both coins on positions i and j. (If they are initially faced up, they will be faced down after the operation and vice versa)




Construct a sequence of at most n+1 operations such that after performing all these operations the coin i will be on position i at the end, facing up.

Note that you do not need to minimize the number of operations.

Input

The first line contains an integer n (3 ≤ n ≤ 2 ⋅ 10^5) — the number of coins.

The second line contains n integers c_1,c_2,...,c_n (1 ≤ c_i ≤ n, c_i ≠ c_j for i≠ j).

Output

In the first line, output an integer q (0 ≤ q ≤ n+1) — the number of operations you used.

In the following q lines, output two integers i and j (1 ≤ i, j ≤ n, i ≠ j) — the positions you chose for the current operation.

Examples

Input


3
2 1 3


Output


3
1 3
3 2
3 1


Input


5
1 2 3 4 5


Output


0

Note

Let coin i facing upwards be denoted as i and coin i facing downwards be denoted as -i.

The series of moves performed in the first sample changes the coins as such:

  * [~~~2,~~~1,~~~3] 
  * [-3,~~~1,-2] 
  * [-3,~~~2,-1] 
  * [~~~1,~~~2,~~~3] 



In the second sample, the coins are already in their correct positions so there is no need to swap.

Difficulty: VERY_HARD
Tags: Graph algorithms

Mathematics

Constructive algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
n = int(input())
A = [0] + list(map(int, input().split()))
seen = [0] * (n + 1)
cycles = []
ans = []
for i in range(1, n + 1):
	cur = []
	j = i
	while not seen[j]:
		cur.append(j)
		seen[j] = 1
		j = A[j]
	if len(cur) > 1:
		cycles.append(cur)

def swap(x, y):
	(A[x], A[y]) = (A[y], A[x])
	ans.append((x, y))
for i in range(1, len(cycles), 2):
	(X, Y) = (cycles[i - 1], cycles[i])
	swap(X[0], Y[0])
	for x in X[1:]:
		swap(x, Y[0])
	for y in Y[1:]:
		swap(y, X[0])
	swap(X[0], Y[0])
if len(cycles) % 2:
	X = cycles[-1]
	if len(X) > 2:
		for x in X[:-2]:
			swap(x, X[-1])
		swap(X[0], X[-2])
		swap(X[-2], X[-1])
		swap(X[0], X[-1])
	else:
		Y = []
		for i in range(1, n + 1):
			if i != X[0] and i != X[1]:
				break
		swap(i, X[0])
		swap(i, X[1])
		swap(i, X[0])
print(len(ans))
for a in ans:
	print(*a)


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

def swap(a, b):
	out.append(str(a + 1) + ' ' + str(b + 1))
	(check[a], check[b]) = (-check[b], -check[a])
vis = [False] * n
head = []
for i in range(n):
	if not vis[i]:
		head.append(i)
		vis[i] = True
		curr = i
		while p[curr] != i:
			curr = p[curr]
			vis[curr] = True
while len(head) >= 2:
	a = head.pop()
	b = head.pop()
	swap(a, b)
	curra = p[a]
	while curra != a:
		swap(b, curra)
		curra = p[curra]
	currb = p[b]
	while currb != b:
		swap(a, currb)
		currb = p[currb]
	swap(a, b)
if len(head) == 1:
	a = head[0]
	if p[a] == a:
		pass
	elif p[p[a]] == a:
		a1 = a
		a2 = p[a]
		a3 = b
		swap(a2, a3)
		swap(a1, a3)
		swap(a2, a3)
	else:
		l = [a, p[a]]
		while p[l[-1]] != a:
			l.append(p[l[-1]])
		k = len(l)
		swap(l[0], l[1])
		for i in range(2, k - 1):
			swap(l[0], l[i])
		swap(l[1], l[k - 1])
		swap(l[0], l[k - 1])
		swap(l[0], l[1])
assert check == list(range(n))
assert len(out) <= n + 1
print(len(out))
print('\n'.join(out))


def swap(i, j):
	(graph[i], graph[j]) = (-graph[j], -graph[i])
	ans.append((i, j))

def solve_pair(x, y):
	swap(x, y)
	i = x
	while graph[-graph[i]] > 0:
		swap(i, -graph[i])
	i = -graph[i]
	while graph[-graph[i]] > 0:
		swap(i, -graph[i])
	swap(i, -graph[i])
n = int(input())
j = 1
graph = [0]
solved = set()
for i in input().split():
	graph.append(int(i))
	if int(i) == j:
		solved.add(j)
	j += 1
ans = []
cycles = set()
for x in range(1, n + 1):
	if not x in solved:
		i = x
		solved.add(i)
		i = graph[i]
		while i != x:
			solved.add(i)
			i = graph[i]
		cycles.add(i)
while len(cycles) > 1:
	solve_pair(cycles.pop(), cycles.pop())
if len(cycles) == 1:
	j = 1
	while not (j == n + 1 or j == graph[j]):
		j += 1
	if j != n + 1:
		solve_pair(j, cycles.pop())
	else:
		(i, j) = (graph[1], graph[graph[1]])
		swap(1, graph[1])
		solve_pair(i, j)
print(len(ans))
for i in ans:
	print(i[0], i[1])


from sys import stdin, stdout
n = int(stdin.readline())
arr = [0] + list(map(int, stdin.readline().split()))
vis = [0] * (n + 1)
ans = []

def cswap(i, j):
	(arr[i], arr[j]) = (-arr[j], -arr[i])
	ans.append((i, j))

def swap_cyc(i, j):
	cswap(i, j)
	curr = i
	while arr[-arr[curr]] > 0:
		cswap(curr, -arr[curr])
	curr = -arr[curr]
	while arr[-arr[curr]] > 0:
		cswap(curr, -arr[curr])
	cswap(curr, -arr[curr])
p = -1
for i in range(1, n + 1):
	if vis[i] == 1:
		continue
	if arr[i] == i:
		continue
	curr = i
	while True:
		vis[curr] = 1
		curr = arr[curr]
		if curr == i:
			break
	if p == -1:
		p = i
	else:
		swap_cyc(p, i)
		p = -1
if p != -1:
	can = False
	for i in range(1, n + 1):
		if arr[i] == i:
			swap_cyc(p, i)
			can = True
			break
	if can == False:
		(t1, t2) = (arr[p], arr[arr[p]])
		cswap(p, t1)
		swap_cyc(t1, t2)
print(len(ans))
[print(i[0], i[1]) for i in ans]


import os, sys, heapq as h, time
from io import BytesIO, IOBase
from types import GeneratorType
from bisect import bisect_left, bisect_right
from collections import defaultdict as dd, deque as dq, Counter as dc
import math, string
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		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 = self.os.read(self._fd, max(self.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 = self.os.read(self._fd, max(self.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:
			self.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')

def getInt():
	return int(input())

def getStrs():
	return input().split()

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

def getStr():
	return input()

def listStr():
	return list(input())

def getMat(n):
	return [getInts() for _ in range(n)]

def isInt(s):
	return '0' <= s[0] <= '9'
MOD = 10 ** 9 + 7

def solve():
	N = getInt()
	A = [0] + getInts()
	used = [False] * (N + 1)
	ans = []
	prev_ = -1

	def swap_(i, j):
		ans.append((i, j))
		(A[i], A[j]) = (-A[j], -A[i])
		return

	def join_cycles(i, j):
		swap_(i, j)
		idx = i
		while A[-A[idx]] > 0:
			swap_(idx, -A[idx])
		idx = -A[idx]
		while A[-A[idx]] > 0:
			swap_(idx, -A[idx])
		swap_(idx, -A[idx])
	for i in range(1, N + 1):
		if A[i] == i:
			used[i] = True
		if used[i]:
			continue
		idx = i
		while True:
			used[idx] = True
			idx = A[idx]
			if idx == i:
				break
		if prev_ == -1:
			prev_ = i
		else:
			join_cycles(prev_, i)
			prev_ = -1
	if prev_ > -1:
		j = 1
		while j <= N and A[j] != j:
			j += 1
		if j <= N:
			join_cycles(prev_, j)
		else:
			(i0, i1) = (prev_, A[prev_])
			swap_(i0, i1)
			j = 1
			while j in [i0, i1]:
				j += 1
			join_cycles(i1, j)
	print(len(ans))
	for (a, b) in ans:
		print(a, b)
	return
solve()