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;

template <class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA... a) {
  while(*sdbg!=',')
    cerr<<*sdbg++;
  cerr<<"="<<h<<","; 
  _dbg(sdbg+1, a...);
}

template<class T> ostream & operator<<(ostream & os, vector<T> V){
  os<<"[";
  for(auto vv: V) os << vv <<",";
  return os << "]";
}
template<class L, class R> ostream & operator <<(ostream & os, pair<L,R> P){
  return os <<"("<<P.first <<","<<P.second <<")";
}

#ifdef DEBUG
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif

const int N = 200005;

int n;
int p[N];
bool vis[N];

vector<pair<int, int>> ans;

void merge(vector<int> A, vector<int> B) {
    ans.push_back({A.back(), B.back()});
    for (int i = 0; i + 1 < A.size(); i++) {
        ans.push_back({A[i], B.back()});
    }
    for (int i = 0; i + 1 < B.size(); i++) {
        ans.push_back({B[i], A.back()});
    }
    ans.push_back({A.back(), B.back()});
}

void oneCycle(vector<int> A) {
    ans.push_back({A[0], A[1]});
    ans.push_back({A[1], A[2]});
    ans.push_back({A[0], A[2]});
    for (int i = 3; i < A.size(); i++) {
        ans.push_back({A[1], A[i]});
    }
    ans.push_back({A[1], A[0]});
}

vector<vector<int>> findCycles() {
    vector<vector<int>> cycles;
    for (int i = 1; i <= n; i++) {
        vis[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        if (vis[i]) continue;
        int w = i;
        vector<int> cycle;
        do {
            cycle.push_back(p[w]);
            w = p[w];
            vis[w] = true;
        } while (w != i);
        cycles.push_back(cycle);
    }
    return cycles;
}

int main() {
    
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
    }
    
    vector<vector<int>> cycles = findCycles();
    
    if (cycles.size() == 1) {
        oneCycle(cycles[0]);
    } else {
        for (int i = 0; i + 1 < cycles.size(); i += 2) {
            merge(cycles[i], cycles[i + 1]);
        }
        
        if (cycles.size() % 2 == 1) {
            merge(cycles.back(), {cycles[0][0]});
        }
    }
    
    printf("%d\n", ans.size());
    
    for (auto p : ans) {
        printf("%d %d\n", p.first, p.second);
    }
    
    return 0;
}