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.
#include <bits/stdc++.h>

#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 210000;
int p[maxn], inv[maxn];
int side[maxn], vis[maxn];

vector<pii> op;

void swp(int i, int j) {
//    cerr << "swp " << i << ' ' << j << '\n';
    assert(i != j);
    side[i] ^= 1;
    side[j] ^= 1;
    op.pb({p[i], p[j]});
    swap(p[i], p[j]);
    swap(inv[p[i]], inv[p[j]]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    int n;
    cin >> n;
    forn(i, n) {
        int x;
        cin >> x;
        --x;
        p[x] = i;
        inv[i] = x;
    }

    int m = -1;
    forn(i, n) {
        if (vis[i]) continue;
        for (int j = i; !vis[j]; j = p[j]) vis[j] = 1;
        if (p[i] == i) continue;
        if (m != -1) swp(m, i), m = -1;
        else m = i;
    }

    cerr << m << '\n';

    if (m != -1) {
        forn(i, n) vis[i] = 0;
        int len = 0;
        for (int j = m; !vis[j]; j = p[j]) vis[j] = 1, ++len;
        if (len < n) {
            int mm = -1;
            forn(i, n) {
                if (side[i] || vis[i]) continue;
                mm = i;
                break;
            }
            assert(mm != -1);
            swp(m, mm);
        } else {
//            cerr << "here\n";
            int x = m, y = inv[x], z = inv[y];
            swp(x, y);
            swp(x, z);
        }
    }

//    forn(i, n) cerr << p[i] << ' ' << side[i] << '\n';

    forn(j, n) {
        if (side[inv[j]]) {
            while (1) {
                int i = inv[j];
                assert(i != j);
                if (side[inv[i]]) break;
                swp(i, inv[i]);
            }
        }
    }

//    forn(i, n) cerr << inv[i] << ' ' << side[inv[i]] << '\n';

    forn(j, n) {
        if (side[j]) {
            while (j != inv[j]) {
                swp(j, p[j]);
            }
//            cerr << j << ":\n";
//            forn(i, n) cerr << p[i] << ' ' << side[i] << '\n';
        }
    }

    assert(op.size() <= n + 1);
//    forn(i, n) cerr << p[i] << ' ' << side[i] << '\n';
    forn(i, n) assert(p[i] == i && !side[i]);

    cout << op.size() << '\n';
    for (auto [x, y]: op) {
        if (x > y) swap(x, y);
        cout << x + 1 << ' ' << y + 1 << '\n';
    }

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}
