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

Solution:
n = int(raw_input())
radj = map(lambda x: int(x) - 1, raw_input().split())
color = [False] * n
ncolored = 0

adj = [0] * n
for i in xrange(n):
    adj[radj[i]] = i

cycles = []
seen = [False] * n
for i in xrange(n):
    if seen[i]:
        continue
    seen[i] = True
    cycle_length = 0
    it = adj[i]
    if it != i:
        cycle_length += 1
    while it != i:
        seen[it] = True
        it = adj[it]
        cycle_length += 1
    if i != adj[i]:
        cycles.append((i, cycle_length))

result = []
def swap(i, j):
    global ncolored
    assert i != j
    result.append((adj[i], adj[j]))
    radj[adj[j]] = i
    radj[adj[i]] = j
    adj[i], adj[j] = adj[j], adj[i]
    color[i] = not color[i]
    if color[i]:
        ncolored += 1
    else:
        ncolored -= 1
    color[j] = not color[j]
    if color[j]:
        ncolored += 1
    else:
        ncolored -= 1

def reduce_cycle(c, cycle_length):
    global ncolored
    it = c
    while cycle_length > 2:
        if color[it] and (ncolored == cycle_length or not color[radj[it]]):
            new_it = radj[it]
            swap(radj[it], it)
            cycle_length -= 1
            it = new_it
        else:
            it = radj[it]

    assert color[it]
    swap(it, adj[it])



for ci in xrange(1, len(cycles), 2):
    a, alen = cycles[ci - 1]
    b, blen = cycles[ci]
    swap(a, adj[b])
    reduce_cycle(a, alen + blen)
    assert ncolored == 0
    
if len(cycles) % 2:
    a, alen = cycles[-1]
    if alen != 2:
        one = a
        two = adj[one]
        three = radj[one]
        swap(one, two)
        swap(two, three)
        reduce_cycle(a, alen)
    else:
        in_place = -1
        for i in xrange(n):
            if adj[i] == i:
                in_place = i
                break
        other = adj[a]
        if not color[a]:
            swap(a, in_place)
            swap(a, other)
            swap(other, in_place)
        

print(len(result))
for a, b in result:
    print a + 1, b + 1