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:
#pragma GCC optimize("O3")
#pragma GCC target("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;

#define FOR(i, a, b) for (int i = a; i <= (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i, a, b) for (int i = (b); i >= a; i--)
#define F0Rd(i, a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto &a : x)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const char nl = '\n';
const int MX = 200001; //check the limits, dummy
int n;
int adj[MX];
bool adj2[MX];
vector<pii> moves;
void pout() {
  cout << moves.size()<<nl;
  F0R(i,moves.size()) {
    cout << moves[i].f<<" "<<moves[i].s<<nl;
  }
}
vector<vi> get_cycles() {
	vector<vi> ret;
	unordered_set<int> seen;
	FOR(i, 1, n) {
		if (seen.find(i) != seen.end()) continue;
		vi r;
		r.pb(i);
    seen.insert(i);
		int cur = adj[i];
		while (cur != i) {
      seen.insert(cur);
			r.pb(cur);
			cur = adj[cur];
		}
		ret.pb(r);
	}
	return ret;
}
void sw(int a, int b) {
	swap(adj[a], adj[b]);
	adj2[a] = !adj2[a];
	adj2[b] = !adj2[b];
	moves.pb({a, b});
}
// c1.size()+c2.size() swaps
vi comb(vi &c1, vi &c2) {
	vi ret(1);
	ret[0] = c1[0];
	sw(c1.back(), c2.back());
  for(int i=0; i<c1.size()-1; i++) {
    sw(c2.back(),c1[i]);
  }
  for(int i=0; i<c2.size()-1; i++) {
    sw(c1.back(), c2[i]);
  }
  sw(c1.back(),c2.back());
	return ret;
}
void solve() {
	F0R(i, n) {
		cin >> adj[i + 1];
	}
	vector<vi> cycles = get_cycles();
	// last 1-element cycle made, used in case there's odd number and we're not done
	vi last(1);
	int k = cycles.size() / 2;
	for (int i = 0; i < k; i++) {
		// pop back the last 2 cycles and organize them
    vi c1 = cycles[2*i];
    vi c2 = cycles[2*i+1];
		last = comb(c1, c2);
	}
	if (cycles.size()&1) {
		if (cycles.size()==1) {
			// originally 1 big cycle
			// swap first with second, swap first with last, run()
			vi c = cycles[0];
      // n+1 moves
			sw(c[0], c[1]);
			sw(c[1], c[2]);
      sw(c[0],c[2]);
      for(int i=3; i<n; i++) {
        sw(c[1],c[i]);
      }
			sw(c[1], c[0]);
		} else {
			// do the "combine" algorithm with last (a cycle of 1)
			comb(last, cycles[cycles.size()-1]);
		}
	}
  pout();
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;
	solve();
}

// read the question correctly (ll vs int)
// template by bqi343