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

Solution:
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
vector < int > di;
vector < int > vis;
vector < vector < int > > cyc;
void dfs(int v, int c)
{
    vis[v] = 1;
    cyc[c].push_back(v);
    if(vis[di[v]] == 0)
        dfs(di[v], c);
}

vector < pair < int , int > > s;
void handle(int i , int j)
{
    s.push_back({cyc[i][0], cyc[j][0]});
    for(int k = 1; k < cyc[i].size(); k++)
        s.push_back({cyc[j][0], cyc[i][k]});
    for(int k = 1; k < cyc[j].size(); k++)
        s.push_back({cyc[i][0], cyc[j][k]});
    s.push_back({cyc[i][0], cyc[j][0]});
}
void handl1(int i)
{
    int n = cyc[i].size();
    int x = cyc[i][n - 1];
    int y = cyc[i][n - 2];
    int v = cyc[i][0];

    s.push_back({x, v});
    for(int k = 1; k < n - 2; k++)
    {
        s.push_back({cyc[i][k], x});
    }

    s.push_back({v, y});
    s.push_back({y, x});
    s.push_back({x, v});
}
int main()
{
    ios::sync_with_stdio(false);
    cout.tie(0);
    int n;
    cin >> n;
    vis.assign(n + 2, 0);
    di.assign(n + 2, 0);
    vector < int > emp;
    cyc.assign(n + 2, emp);
    for(int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        di[i] = x;
    }
    int c = 0;

    for(int i = 1; i <= n; i ++)
    {
        if(vis[i] == 0)
        {
            dfs(i , c++);
        }
    }
    if(c == n)
    {
        cout << 0 << endl;
        return 0;
    }
    int j = -1;
    int u = - 1;
    for(int i = 0; i < cyc.size(); i++)
    {
        if(j != -1 && cyc[i].size() > 1)
        {
            handle(i , j);
            u = cyc[i][0];
            j = -1;
        }
        else
            if(cyc[i].size() > 1)
                j = i;
        if(cyc[i].size() == 1)
            u = cyc[i][0];
    }

    if(j != -1 && c == 1)
        handl1(0), j = -1;

    if(j != -1)
    {
        cyc[c].push_back(u);
        handle(c, j);
    }
    cout << s.size() << endl;
    for(int k = 0; k < s.size(); k++)
    {
        cout << s[k].first << " " << s[k].second << endl;
    }
    return 0;
}