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>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
#define rep(i,n) for (int i=0;i<(n);++i)
#define REP(i,n) for (int i=1;i<=(n);++i)
#define all(x) x.begin(),x.end()
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define RI(x) scanf("%d",&x)
#define RII(x,y) scanf("%d%d",&x,&y)

int n,N=0;
int a[200005];
bool vis[200005];
vector<int> cyc[200005];

int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	REP(i,n) cin>>a[i];
	REP(i,n) if (!vis[i]){
		vis[i]=1;
		cyc[N].pb(i);
		int u=i;
		while (!vis[a[u]]){
			u=a[u];vis[u]=1;cyc[N].pb(u);
		}
		N++;
	}
	if (N&1) cout<<n+1<<endl;
	else cout<<n<<endl;
	for (int i=0;(i^1)<N;i+=2){
		cout<<cyc[i][0]<<' '<<cyc[i^1][0]<<endl;
		for (int j=1;j<cyc[i].size();++j) cout<<cyc[i][j]<<' '<<cyc[i^1][0]<<endl;
		for (int j=1;j<cyc[i^1].size();++j) cout<<cyc[i^1][j]<<' '<<cyc[i][0]<<endl;
		cout<<cyc[i][0]<<' '<<cyc[i^1][0]<<endl;
	}
	if (N==1){
		// siz == n >=3
		cout<<cyc[0][n-1]<<' '<<cyc[0][n-3]<<endl;
		for (int j=0;j<n-3;++j) cout<<cyc[0][j]<<' '<<cyc[0][n-3]<<endl;
		cout<<cyc[0][n-3]<<' '<<cyc[0][n-2]<<endl;
		cout<<cyc[0][n-2]<<' '<<cyc[0][n-1]<<endl;
		cout<<cyc[0][n-1]<<' '<<cyc[0][n-3]<<endl;
	}
	else if (N&1){// can lend one from N-2
		cout<<cyc[N-2][0]<<' '<<cyc[N-1][0]<<endl;
		for (int j=1;j<cyc[N-1].size();++j) cout<<cyc[N-1][j]<<' '<<cyc[N-2][0]<<endl;
		cout<<cyc[N-2][0]<<' '<<cyc[N-1][0]<<endl;
	}
	
	return 0;
}