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 <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define FOR(ind,end) for(ind = 0; ind < end; ind++)
#define FOR1(ind,begin,end) for(ind=begin; ind<end; ind++)
#define rFOR(ind,end) for(ind=end-1; ind>=0; ind--)
#define EACH(ptr,cont) for(auto ptr: cont)
int i,j,k;
const int mx = 200000;
int mod = 1000000007;
int alt_mod = 998244353;
const int inf = 5e18;
//useful for input processing
template<class T>void setzero(T *begin, T *end){for(auto x=begin;x<end;x++)*x=0;}
template<class T>void setval(T *begin, T *end, int val){for(auto x=begin;x<end;x++)*x=(T)val;}
template<class T>void read(T *begin, T *end){for(auto x=begin;x<end;x++)cin>>*x;}
template<class T>void print(T *begin, T *end){for(auto x=begin;x<end;x++)cout<<*x <<" ";cout<<"\n";}
template<class T>void print(vector<T>v){for(auto x:v)cout<<x<<" ";cout<<"\n";}
template<class T>bool cmp_pair_first(pair<T,T> a, pair<T,T> b){return a.first < b.first;}
template<class T>bool cmp_vec_first(vector<T> a, vector<T> b){return a[0]<b[0];}
template<class T>void sort_by_first(pair<T,T> *begin,pair<T,T> *end){sort(begin,end,cmp_pair_first<T>);}
template<class T>void sort_by_first(vector<T> *begin, vector<T> *end){sort(begin,end,cmp_vec_first<T>);}

template<class T>int sum(int begin,int end,T f){int ans=0;for(int ind=begin;ind<=end;ind++)ans+=f(ind);return ans;}
template<class T>int argmin(int begin,int end,T f){int ans=begin;for(int ind=begin+1;ind<=end;ind++)if(f(ind)<f(ans))ans=ind;return ans;}
template<class T>int argmax(int begin,int end,T f){int ans=begin;for(int ind=begin+1;ind<=end;ind++)if(f(ind)>f(ans))ans=ind;return ans;}
template<class T>int min(int begin,int end,T f){return f(argmin(begin,end,f));}
template<class T>int max(int begin,int end,T f){return f(argmax(begin,end,f));}

//-----------------------------------//
//         Begin coding here         //
//-----------------------------------//

int n, a[200005], pos[200005];
vector<vector<int>> cyc;
vector<pair<int,int>> ans;

void flip(int p, int q){
   swap(pos[p],pos[q]);
   ans.push_back(make_pair(pos[p],pos[q]));
}

void fix_one_cyc(int p){
   int m = cyc[p].size();
   if(m==1) return;
   if(m==2){
      i = 1;
      while(i == cyc[p][0] || i == cyc[p][1]) i++;
      flip(cyc[p][1],i);
      flip(cyc[p][0],cyc[p][1]);
      flip(cyc[p][0],i);
      return;
   }
   flip(cyc[p][0],cyc[p][m-1]);
   flip(cyc[p][m-1],cyc[p][1]);
   flip(cyc[p][0],cyc[p][m-1]);
   for(i=1; i<=m-2; i++){
      flip(cyc[p][i], cyc[p][i+1]);
   }
}

void fix_two_cyc(int a, int b){
   int r = cyc[a].size(), s = cyc[b].size();
   //a0, a1 done
   flip(cyc[a][0],cyc[b][0]);
   flip(cyc[a][1],cyc[b][1]);
   for(i=1; i<=s-2; i++){
      flip(cyc[b][i],cyc[b][i+1]);
   }
   flip(cyc[b][s-1],cyc[a][0]);
   for(i=1; i<=r-2; i++){
      flip(cyc[a][i],cyc[a][i+1]);
   }
   flip(cyc[a][r-1],cyc[b][0]);
}

void solve(){
   cin >> n;
   read(a+1,a+n+1);
   FOR1(i,1,n+1) pos[a[i]] = i;
   bool vis[n+1];
   //preparing cycles
   FOR1(i,1,n+1) vis[i] = false;
   FOR1(i,1,n+1){
      if(vis[i]) continue;
      vector<int> v;
      j = i;
      while(!vis[j]){
         v.push_back(j);
         vis[j] = true;
         j = a[j];
      }
      cyc.push_back(v);
   }

   int pre = -1;
    
   FOR(j,cyc.size()){
      if(cyc[j].size() == 1) continue;
      if(pre == -1){
         pre = j; 
      }
      else{
         fix_two_cyc(pre,j);
         pre = -1;
      }
   }
   if(pre != -1) fix_one_cyc(pre);
   cout << ans.size() << "\n";
   for(auto p : ans){
      cout << p.first << " " << p.second << "\n";
   }
}

signed main(){
   ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   long tc=1;
   //cin >> tc; //COMMENT HERE IF A PROBLEM HAS ONLY ONE TEST CASE. 
   while(tc--){
      solve();
   }
   return 0;
}