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 F first
#define S second
#define pii pair<int, int>
#define pb push_back

using namespace std;

typedef long long ll;
typedef long double ld;

const int maxN = 2e5 + 10;

	
vector <pii> ans;
vector <vector <int> > cycles;
int p[maxN];
bool vis[maxN];

void solve(vector <int> c) {
	int l = c.size();
	for (int i=0; i<l-1; i++)
		ans.pb({c[0], c[i + 1]});
	//cout << c[0] << ' ' << c[i + 1] << '\n';
	return ;
}
void print() {
	
	cout << ans.size() << '\n';
	for (auto X : ans)
		cout << X.F << ' ' << X.S << '\n';
	exit(0);
}

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

	int n; cin >> n;
	for (int i=1; i<=n; i++)
		cin >> p[i];

	for (int i=1; i<=n; i++) {
		if(vis[i]) continue ;
		int curr = i;
		vector <int> c;
		while(!vis[curr]) {
			vis[curr] = true;
			c.pb(curr);
			curr = p[curr];
		}
		if((int)c.size() == 1) continue ;

		cycles.pb(c);
	}
	
	int l = cycles.size();
	for (int i=0; i<l/2; i++) {
		//mere i, i + 1
		int i1 = cycles[2*i][0], i2 = cycles[2*i + 1][0];
		ans.pb({i1, i2});
		//cout << i1 << ' ' << i2 << '\n';
		//cout << p[i1] << ' ' << p[i2] << '\n';
		ans.pb({p[i1], p[i2]});
		
		int curr = p[p[i1]];
		vector <int> c1;
		c1.pb(p[i2]); c1.pb(p[p[i1]]);
		while(curr != i1)
		{
			c1.pb(p[curr]);
			curr = p[curr];
		}
		solve(c1);

		curr = p[p[i2]];
		vector <int> c2;
		c2.pb(p[i1]); c2.pb(p[p[i2]]);
		while(curr != i2) 
		{
			c2.pb(p[curr]);
			curr = p[curr];
		}
		solve(c2);
	}
	
	if(l % 2 == 0)
		print();

	int k = cycles[l - 1][0];
	if(cycles[l - 1].size() == 2) {
		int i1 = cycles[l - 1][0], i2 = cycles[l - 1][1];
		int i3 = 1;
		if(i3 == i1 or i3 == i2) {
			i3 = n;
			if(i3 == i1 or i3 == i2) i3 = 2;
		}
		ans.pb({i1, i3});
		ans.pb({i2, i3});
		ans.pb({i1, i3});
		print();

	}
	
	ans.pb({k, p[k]});
	//cout << k << " " << p[k] << '\n';
	ans.pb({p[k], p[p[k]]});
	//cout << p[k] << " " << p[p[k]] << '\n';
	ans.pb({p[p[k]], p[p[p[k]]]});
	//cout << p[p[k]] << ' ' << p[p[p[k]]] << '\n';
	ans.pb({p[p[p[k]]], p[k]});
	//cout << p[p[p[k]]] << ' ' << p[k] << '\n';

	if(cycles[l - 1].size() == 3)
		print();

	vector <int> c3;
	c3.pb(p[p[k]]);
	c3.pb(p[p[p[p[k]]]]);
	int curr = p[p[p[p[k]]]];
	for (int i=0; i<(int)cycles[l - 1].size() - 4; i++) {
		c3.pb(p[curr]);
		curr = p[curr];
	}

	solve(c3);
	print();
}