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

Solution:
import java.util.*;import java.io.*;import java.math.*;
public class Main
{
    public static void process()throws IOException
    {
        int n=ni();
        int[]A=new int[n+1];
        for(int i=1;i<=n;i++)
            A[i]=ni();
        boolean[]vis=new boolean[n+1];
        ArrayList<ArrayList<Integer>> list=new ArrayList<>();
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                ArrayList<Integer>curr=new ArrayList<>();
                int now=A[i];
                while(now!=i)
                {
                    curr.add(now);
                    vis[now]=true;
                    now=A[now];
                }
                curr.add(i);
                if(curr.size()>1)
                    list.add(curr);
            }
        }
        ArrayList<String> ans=new ArrayList<>();
        for(int i=0;i<list.size();i+=2)
        {
            if(i+1<list.size())
            {
                for(int j=0;j<list.get(i+1).size();j++)
                    ans.add(list.get(i).get(0)+" "+list.get(i+1).get(j));
                for(int j=1;j<list.get(i).size();j++)
                    ans.add(list.get(i+1).get(0)+" "+list.get(i).get(j));
                ans.add(list.get(i+1).get(0)+" "+list.get(i).get(0));
            }
            else
            {
                if(list.get(i).size()==2)
                {
                    int ind=0;
                    for(int j=1;j<=n;j++)
                        if(A[j]==j)
                            ind=j;
                    if(ind==0)
                        ind=list.get(0).get(0);
                    ans.add(ind+" "+list.get(i).get(0));
                    ans.add(ind+" "+list.get(i).get(1));
                    ans.add(ind+" "+list.get(i).get(0));
                }
                else
                {
                    //pn(list.get(i));
                    int x=list.get(i).size();
                    ans.add(list.get(i).get(x-1)+" "+list.get(i).get(x-2));
                    ans.add(list.get(i).get(x-1)+" "+list.get(i).get(x-3));
                    for(int j=list.get(i).size()-1;j>1;j--)
                        ans.add(list.get(i).get(x-2)+" "+list.get(i).get(x-j-1));
                    ans.add(list.get(i).get(x-1)+" "+list.get(i).get(x-2));
                }
            }
        }
        pn(ans.size());
        for(String x:ans)
            pn(x);
    }

    static AnotherReader sc;
    static PrintWriter out;
    public static void main(String[]args)throws IOException
    {
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
        if(oj){sc=new AnotherReader();out=new PrintWriter(System.out);}
        else{sc=new AnotherReader(100);out=new PrintWriter("output.txt");}
        int t=1;
       // t=ni();
        while(t-->0) {process();}
        out.flush();out.close();  
    }

    static void pn(Object o){out.println(o);}
    static void p(Object o){out.print(o);}
    static void pni(Object o){out.println(o);out.flush();}
    static int ni()throws IOException{return sc.nextInt();}
    static long nl()throws IOException{return sc.nextLong();}
    static double nd()throws IOException{return sc.nextDouble();}
    static String nln()throws IOException{return sc.nextLine();}
    static int[] nai(int N)throws IOException{int[]A=new int[N];for(int i=0;i!=N;i++){A[i]=ni();}return A;}
    static long[] nal(int N)throws IOException{long[]A=new long[N];for(int i=0;i!=N;i++){A[i]=nl();}return A;}
    static long gcd(long a, long b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int gcd(int a, int b)throws IOException{return (b==0)?a:gcd(b,a%b);}
    static int bit(long n)throws IOException{return (n==0)?0:(1+bit(n&(n-1)));}

/////////////////////////////////////////////////////////////////////////////////////////////////////////

    static class AnotherReader{BufferedReader br; StringTokenizer st;
    AnotherReader()throws FileNotFoundException{
    br=new BufferedReader(new InputStreamReader(System.in));}
    AnotherReader(int a)throws FileNotFoundException{
    br = new BufferedReader(new FileReader("input.txt"));}
    String next()throws IOException{
    while (st == null || !st.hasMoreElements()) {try{
    st = new StringTokenizer(br.readLine());}
    catch (IOException  e){ e.printStackTrace(); }}
    return st.nextToken(); } int nextInt() throws IOException{
    return Integer.parseInt(next());}
    long nextLong() throws IOException
    {return Long.parseLong(next());}
    double nextDouble()throws IOException { return Double.parseDouble(next()); }
    String nextLine() throws IOException{ String str = ""; try{
    str = br.readLine();} catch (IOException e){
    e.printStackTrace();} return str;}}
   
/////////////////////////////////////////////////////////////////////////////////////////////////////////////
}