Problem: 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.

Solution (in PYTHON3):

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