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:
/*long long or int&the MAX_INT or MIN_INT*/
/*the size of a[]&inline*/
/*xx 396*/
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
template<class T>inline void checkmin(T &a,const T &b){if(b<a)a=b;}
template<class T>inline void checkmax(T &a,const T &b){if(b>a)a=b;}
const int maxn=2e5+10;
int nxt[maxn],pos[maxn],n;
bool state[maxn],vis[maxn];
vector<pair<int,int> >ans;
vector<vector<int> >cir;
vector<int>v;
void dfs(int x){
	v.pb(x);vis[x]=true;if(!vis[nxt[x]])dfs(nxt[x]);
}
void op(int x,int y){
	swap(nxt[x],nxt[y]);swap(pos[nxt[x]],pos[nxt[y]]);
//	cout<<x<<" "<<y<<" "<<nxt[x]<<" "<<nxt[y]<<endl;
	ans.pb(mp(nxt[x]+1,nxt[y]+1));
//	cout<<state[x]<<" "<<state[y]<<endl;
	state[x]=1-state[x];state[y]=1-state[y];
//	cout<<state[x]<<" "<<state[y]<<endl;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		int x;cin>>x;x--;nxt[x]=i;pos[i]=x;state[x]=true;
	}	
//	for(int i=0;i<n;i++)cout<<nxt[i]+1<<" ";cout<<endl;
	for(int i=0;i<n;i++){
		v.clear();dfs(i);
		if((int)v.size()!=1)cir.pb(v);
	}
	for(int ID=0;ID<(int)cir.size();ID+=2){
		int a=ID,b=ID+1;
		if(ID+1>=(int)cir.size())continue;
		op(cir[a][0],cir[b][0]);int x=cir[a][0],y,z;
	//	for(int i=0;i<n;i++)cout<<pos[i]<<" ";cout<<endl;
		for(int i=0;i<(int)cir[a].size()-1;i++){
		//	for(int j=0;j<n;j++)cout<<pos[j]<<" ";cout<<endl;
		//	for(int j=0;j<n;j++)cout<<state[pos[j]]<<" ";cout<<endl;
			y=pos[x],op(x,pos[x]),x=y;
		//	for(int j=0;j<n;j++)cout<<state[pos[j]]<<" ";cout<<endl;
		}
		x=cir[b][0];
		for(int i=0;i<(int)cir[b].size()-2;i++)y=pos[x],op(x,pos[x]),x=y;
	//	for(int i=0;i<n;i++)cout<<pos[i]<<" ";cout<<endl;
	//	for(int i=0;i<n;i++)cout<<state[pos[i]]<<" ";cout<<endl;
		for(int i=0;i<(int)cir[a].size();i++){
			if(nxt[cir[a][i]]!=cir[a][i]&&state[cir[a][i]]==false)x=y,y=cir[a][i];
			if(pos[cir[a][i]]!=cir[a][i]&&state[cir[a][i]]==true)z=cir[a][i]; 
		}
		for(int i=0;i<(int)cir[b].size();i++){
			if(nxt[cir[b][i]]!=cir[b][i]&&state[cir[b][i]]==false)x=y,y=cir[b][i];
			if(nxt[cir[b][i]]!=cir[b][i]&&state[cir[b][i]]==true)z=cir[b][i];
		}
	//	cout<<x<<" "<<y<<" "<<z<<endl;
		if(nxt[x]!=y)swap(x,y);
		op(x,z);op(y,z);
	}
	if((int)cir.size()&1){
		vector<int>tmp=cir[(int)cir.size()-1];
		if((int)tmp.size()==2){
			int x=tmp[0],y=tmp[1],z;
			for(int i=0;i<n;i++)if(i!=x&&i!=y)z=i;
			op(x,z);op(x,y);op(y,z);
		}
		else{
			int x=pos[tmp[0]],y,z;op(tmp[0],pos[tmp[0]]);
			for(int i=0;i<(int)tmp.size()-3;i++)y=pos[x],op(x,pos[x]),x=y;
			x=tmp[0];
			for(int i=1;i<(int)tmp.size();i++){
				if(nxt[tmp[i]]!=tmp[i]&&state[tmp[i]]==false)y=tmp[i];
				if(nxt[tmp[i]]!=tmp[i]&&state[tmp[i]]==true)z=tmp[i];
			}
			op(x,z);swap(x,z);
			if(nxt[x]!=y)swap(x,y);
		//	cout<<x<<" "<<y<<" "<<z<<endl;
			op(x,z);op(y,z);
		}
	}
	cout<<(int)ans.size()<<endl;
	for(int i=0;i<(int)ans.size();i++)cout<<ans[i].fst<<" "<<ans[i].snd<<endl;
	return 0;
}
/*
7 
2 3 1 5 6 7 4
*/