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>
#define pii pair<int, int>
#define f first
#define s second
#define ll long long
#define oo 1000000000
#define piii pair<pii, int>
#define pb push_back

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int>p(n + 1);
    for(int i = 1; i <= n; ++i) {
        cin >> p[i];
    }
    vector<bool>visited(n + 1, false);
    vector<vector<int>>cycles;
    vector<pii>res;
    for(int i = 1; i <= n; ++i) {
        if(!visited[i]) {
            vector<int>cycle;
            int node = i;
            while(!visited[node]) {
                cycle.pb(node);
                visited[node] = true;
                node = p[node];
            }
            if((int)cycle.size() >= 2) {
                cycles.pb(cycle);
            }
        }
    }

    while((int)cycles.size() > 1) {
        vector<int>cycle1 = cycles.back();
        cycles.pop_back();
        vector<int>cycle2 = cycles.back();
        cycles.pop_back();

        if((int)cycle1.size() > (int)cycle2.size()) {
            swap(cycle1, cycle2);
        }
        reverse(cycle2.begin(), cycle2.end());
        for(int i = 0; i < (int)cycle1.size(); ++i) {
            res.pb({cycle1[i], cycle2[i]});
            swap(p[cycle1[i]], p[cycle2[i]]);
        }
        for(int i = 0; i < (int)cycle1.size(); ++i) {
            while(p[cycle1[i]] != cycle1[i]) {
                res.pb({cycle1[i], p[cycle1[i]]});
                swap(p[cycle1[i]], p[p[cycle1[i]]]);
            }
        }
    }

    if(!cycles.empty()) {
        int inpos = 0;
        for(int i = 1; i <= n && inpos == 0; ++i) {
            if(p[i] == i) {
                inpos = i;
            }
        }
        if(inpos) {
            for(int i = 0; i < (int)cycles[0].size(); ++i) {
                res.pb({inpos, cycles[0][i]});
                swap(p[inpos], p[cycles[0][i]]);
            }
            res.pb({inpos, cycles[0][0]});
            swap(p[inpos], p[cycles[0][0]]);
        }else { /// cycle size > 2, otherwise there will be some i, where p[i] = i
            int i = cycles[0].front();
            int j = cycles[0].back();
            int idx = p[i];
            res.pb({j, p[i]});
            swap(p[j], p[p[i]]);
            res.pb({i, j});
            swap(p[i], p[j]);
            while(p[idx] != idx) {
                res.pb({p[idx], idx});
                swap(p[p[idx]], p[idx]);
            }
        }
    }

    cout << res.size() << '\n';
    for(pii pr : res) {
        cout << pr.f << " " << pr.s << '\n';
    }
}
int main()
{
    int t = 1;
    // cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}