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 For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define pii pair<int,int>
#define fi first
#define se second
#define PB push_back
#define ll long long
#define ull unsigned long long
#define pll pair<ll,ll> 
#define y1 orzkcz
using namespace std;

const int N=200005;
int n,a[N],fl[N],vis[N];
vector<int> temp2;
vector<pii> op;
void work(int x,int y){
	assert(x!=y);
	swap(a[x],a[y]);
	swap(fl[x],fl[y]);
	fl[x]^=1; fl[y]^=1;
	op.PB(pii(x,y));
}
void Merge(vector<int> v1,vector<int> v2){
	work(v1[0],v2[0]);
	for (;a[v1[0]]!=v2[0];work(v1[0],a[v1[0]]));
	for (;a[v2[0]]!=v1[0];work(v2[0],a[v2[0]]));
	work(v1[0],v2[0]);
}
void find(int x){
	vector<int> temp;
	for (;!vis[x];x=a[x]) temp.PB(x),vis[x]=1;
	if (temp2.size()) Merge(temp,temp2),temp2.resize(0);
	else temp2=temp;
}
void solve2(vector<int> v2){
	work(v2[0],v2[2]);
	work(v2[0],v2[1]);
	for (;a[v2[2]]!=v2[0];work(v2[2],a[v2[2]]));
	work(v2[0],v2[2]); 
}
int main(){
	scanf("%d",&n);
	//For(i,1,n) a[i]=i%n+1;
	//random_shuffle(a+1,a+n+1);
	For(i,1,n) scanf("%d",&a[i]);
	For(i,1,n) if (i!=a[i]&&!vis[i]) find(i);
	if (temp2.size()){
		if (temp2.size()!=n){
			For(i,1,n) if (i==a[i]){
				Merge(temp2,vector<int>{i});
				break;
			}
		}
		else solve2(temp2);
	}
	For(i,1,n) assert(a[i]==i&&!fl[i]);
	printf("%d\n",op.size());
	for (auto i:op) printf("%d %d\n",i.fi,i.se);
}
/*
2   3  1  5  6  4
-5  3  1  -2 6  4
1
2  3  4  5  6  7  8  1  9
2  3  4  5  6  7  8  -9  -1  *1
1  2  3  4  5  6  7  -9  -8  *8

2  3  4  5  6  7  8  1 
-4 3 -2
-3 4 -2


 
*/