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:
//Common Header Simple over C++11
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define STLsz(x) ((int)(x).size())
#define memset0(x) memset((x),0,sizeof(x));
//#define endl '\n'
#define count2(x) __builtin_popcount(x)
#define countleadingzero(x) __builtin_clz(x)
#define dd(x) cerr << #x << " = " << x << ' ';
#define de(x) cerr << #x << " = " << x << endl;
//inline char nc() {
//  static char buf[1000000], *p = buf, *q = buf;
//  return p == q && (q = (p = buf) + fread(buf, 1, 1000000, stdin), p == q)
//             ? EOF
//             : *p++;
//}
inline ll rd(){//LLONG_MIN LMAX=9,223,372,036,854,775,807
	ll s=0,w=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9')s=s*10+ch-'0',ch=getchar();
	return s*w;
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	// 题意 给一个1--n的排列 n>3 一个操作是交换两位并取反 构造一个最多n+1的操作序列使得最终序列变成1,2,3...n 
	/* 
	Editor: INFINT
	Time: 2021-03-03 
	Solution:
	定义这个排列为a 排列下标为i的元素的值为ai 
	定义“对齐”为i=ai 
	取出所有不对齐的元素 构成一个群 
	性质一：如果是一个长n>2循环内的不对齐 可以构造一个方法通过n+1次的操作使得得到对齐 
	2 3 1
	-3 -2 1
	-3 -1 2
	-2 -1 3
	1 2 3
	随意取两个元素进行交换产生两个负数 此处为了方便取 第一 第二个 然后 选择这两个元素中换后目标位置不是负数的进行换
	负号被传递到来的那个元素上 选两个其中一个必能换的继续换到只剩下两个 自己互换都能归位为止
	性质二：等于二的循环可以通过添加额外一个元素变成性质一的情况
	性质三：任意两个循环可以通过跨循环选择各一个元素互换在n次操作内完成 
	*/
	int n,cnt=1;cin>>n;
	
	vector<int>vi(n+1);
	vector<int>yg;
	vector<vector<int>>circle;
	{
		vector<int>ng,fa(n+1);
		function<int(int)>find=[&](int x){return fa[x]==x?x:fa[x]=find(fa[x]);};
		for(int i=1;i<=n;++i)cin>>vi[i],fa[i]=i;
		for(int i=1;i<=n;++i){
			if(vi[i]==i)yg.pb(i);
			else{
				ng.pb(i);
				int fu=find(i),fv=find(vi[i]);
				if(fu!=fv)fa[fu]=fv;
			}
		}
		
		{
			map<int,int>Index;
			for(auto i:ng){
				int fi=find(i);
				if(Index.count(fi)==0)	Index[fi]=cnt,cnt++,circle.pb({});
				circle[Index[fi]-1].pb(i);
			}
		}	
	}
	circle.shrink_to_fit();
	for(auto &i:circle)i.shrink_to_fit();
	vector<pii>ans;
	function<void(int,int)>op=[&](int x,int y){
		ans.pb({x,y});swap(vi[x],vi[y]);vi[x]*=-1;vi[y]*=-1;
	};
	for(int i=STLsz(circle)-1;i>=0;i-=2){
		if(i==0){//one
			auto &arr=circle[i];
			if(STLsz(arr)>2){
				int n1=arr[0],n2;// 特殊构造会自己跑到自己的情况 防止中途出现 
				for(int p=1;p<STLsz(arr);++p){
					if(arr[0]==vi[arr[p]]){
						n2=arr[p];break;
						arr.erase(arr.begin()+p);
					}
				}
				op(n1,n2);
				if(-vi[n1]==n1){op(n1,arr[1]);}
				else if(-vi[n2]==n2){op(n2,arr[1]);}
				while(1){
					if(-vi[n1]==n2&&-vi[n2]==n1){
						op(n1,n2);
						break;
					}
					else{
						if(vi[-vi[n1]]>0)	op(-vi[n1],n1);
						else if(vi[-vi[n2]]>0)	op(-vi[n2],n2);
					}
				}
			}
			else{
				int n1=arr[0],n2=yg[0];
				op(n1,n2);
				if(-vi[n1]==n1){op(n1,arr[1]);}
				else if(-vi[n2]==n2){op(n2,arr[1]);}
				while(1){
					if(-vi[n1]==n2&&-vi[n2]==n1){
						op(n1,n2);
						break;
					}
					else{
						if(vi[-vi[n1]]>0)	op(-vi[n1],n1);
						else	op(-vi[n2],n2);
					}
				}
			}
		}
		else{//two
			auto &arr1=circle[i];
			auto &arr2=circle[i-1];
			op(arr1[0],arr2[0]);//merge
			int n1=arr1[0],n2=arr2[0];
			yg.pb(n1);yg.pb(n2);
			while(1){
				if(-vi[n1]==n2&&-vi[n2]==n1){
					op(n1,n2);
					break;
				}
				else{
					if(vi[-vi[n1]]>0)	op(-vi[n1],n1);
					else	op(-vi[n2],n2);
				}
			}
		}
	}
	cout<<ans.size()<<'\n';
	for(auto &p:ans){
		cout<<p.fi<<" "<<p.se<<'\n';
	}
	return 0;
}