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 <set>
#include <map>
#include <cmath>
#include <queue>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <assert.h>
		
#define line cerr<<"--------------------\n"
#define see(x) cerr<<x<<" "
#define seeln(x) cerr<<x<<endl
#define out(x) cerr<<#x<<" = "<<x<<" "
#define outln(x) cerr<<#x<<" = "<<x<<endl
#define outarr(x,l,r) cerr<<#x"["<<l<<"-"<<r<<"] = "; for (int _i=l;_i<=r;++_i) cerr<<x[_i]<<" ";cerr<<endl;

using namespace std;
template <class T> bool umin(T &x,T y) {return y<x? x=y,1: 0;}
template <class T> bool umax(T &x,T y) {return y>x? x=y,1: 0;}

/*
每个点都有一条出边、一条入边；相当于有很多个环。
每次可以交换两个顶点的出边，并且 **指向的** 两个点的符号去反。
目标是让所有点变成自环，且点都是正点。

考虑如果交换相邻的两个顶点，就可以将一个点孤立
这样虽然可以在 (n-1) 步让一个环上所有点孤立，但会导致存在两个负点

考虑同时处理两个环。可以用一步操作将两个环合并成一个环，并且恰有两个负点。
可以每次将一个负点变成自环，并创造一个新的负点，所以环上始终保持有两个负点，
最后交换由两个负点组成的二元环，就可以在 (n-1) 步里解决。

如果环数是奇数，最后一个环可以结合一个自环解决
特殊地，如果环数是 1，需要先搞一个自环然后放回去使之变成一个包含两个负点的环
*/

#define P pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
int n,tot = 0,c[N],vs[N],fg[N],st[N];
vector<P> ans;

void swp(int x,int y) {
	swap(c[x], c[y]);
	fg[c[x]] ^= 1; fg[c[y]] ^= 1;
	ans.push_back(P(x,y));
}

// 包含两个负点的环
void dfs(int u,int to) {
	if(u == to) return ;
	dfs(c[u], to);
	swp(u, c[u]);
}
void solve(int u,int v) {
	/*
	交换的是 c_i，也是 c_i 在变号
	*/
	while(c[u] != v) swp(u,c[u]);
	while(c[v] != u) swp(v,c[v]);
	swp(u,v);
}

signed main()
{
	cin >> n; 
	for(int i = 1; i <= n; ++i) cin >> c[i];

	for(int i = 1; i <= n; ++i) {
		if(!vs[i]) {
			st[++tot] = i;
			int u = i;
			while(!vs[u]) {
				vs[u] = 1;
				u = c[u];
			}
		}
	}
	memset(fg,0,sizeof(fg));

	// cout << tot << "?\n";

	if(tot == 1) {
		int t = c[st[1]];
		swp(st[1], t);
		swp(t, c[st[1]]);
		solve(st[1], t);
	}
	else {
		for(int i = 1; i < tot; i += 2) {
			swp(st[i],st[i+1]);
			solve(st[i],st[i+1]);
		}
		if(tot & 1) {
			swp(st[tot], st[1]);
			solve(st[tot], st[1]);
		}
	}

	cout << ans.size() << endl;
	for(int i = 0; i < (int)ans.size(); ++i)
		cout << ans[i].fi << " " << ans[i].se << endl;

	// for(int i = 1; i <= n; ++i) cout << fg[i] << " "; cout << endl;
	// for(int i = 1; i <= n; ++i) cout << c[i] << " "; cout << endl;

	return 0;
}