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;
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma,tune=native")

#define ll long long
#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
//#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
const int maxn=200005;
//i_am_noob
//#define wiwihorz  
int n,to[maxn];
bool a[maxn],vis[maxn];
vector<int> vec,vec1,vec2;
vector<pii> res;

void Swap(int x, int y){
    swap(to[x],to[y]);
    a[x]^=1,a[y]^=1;
    res.pb({to[x]+1,to[y]+1});
}

void hhhhauraorz(){
    cin >> n;
    rep(n){
        int x;
        cin >> x;
        to[x-1]=i;
    }
    rep(n){
        if(vis[i]) continue;
        vis[i]=true;
        if(to[i]==i) continue;
        vec.pb(i);
        for(int j=to[i]; j!=i; j=to[j]) vis[j]=true;
    }
    rep(sz(vec)/2){
        int x=vec[2*i],y=vec[2*i+1];
        Swap(x,y);
        vec1.clear(),vec2.clear();
        for(int j=to[x]; j!=y; j=to[j]) vec1.pb(j);
        vec1.pb(y);
        for(int j=to[y]; j!=x; j=to[j]) vec2.pb(j);
        vec2.pb(x);
        rep3(j,sz(vec1)-2,0) Swap(vec1[j],vec1[j+1]);
        rep3(j,sz(vec2)-2,0) Swap(vec2[j],vec2[j+1]);
        Swap(vec1[0],vec2[0]);
    }
    if(sz(vec)&1){
        int x=vec.back();
        vec1={x};
        for(int i=to[x]; i!=x; i=to[i]) vec1.pb(i);
        if(sz(vec1)==2){
            int y;
            rep(n) if(i!=x&&i!=vec1[1]){
                y=i;
                break;
            }
            Swap(y,x);
            Swap(x,vec1[1]);
            Swap(y,vec1[1]);
        }
        else{
            Swap(x,vec1.back());
            Swap(x,vec1[1]);
            rep3(i,sz(vec1)-2,2) Swap(vec1[i],vec1[i+1]);
            Swap(x,vec1[2]);
            Swap(x,vec1[1]);
        }
    }
    print(sz(res));
    for(auto& [x,y]: res) print(x,y);
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    #ifdef i_am_noob
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    freopen("output2.txt","w",stderr);
    #endif
    int t;
    #ifdef wiwihorz
    cin >> t;
    #else
    t=1;
    #endif
    while(t--) hhhhauraorz();
    return 0;
}