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:
/** I can do this all day **/

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;

typedef long long                   ll;
typedef long double                 ld;
typedef pair<int,int>               pii;
typedef pair<ll,ll>                 pll;
#define all(x)                      (x).begin(),(x).end()
#define F                           first
#define S                           second
#define Mp                          make_pair
#define SZ(x)			    		(int)x.size()
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io                     freopen("in.txt" , "r+" , stdin) ; freopen("out.txt" , "w+" , stdout);

const int N = 1e6 + 10;
const ll mod = 1e9 + 7;
const ll mod2 = 998244353;
const ll inf = 8e18;
const int LOG = 22;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

int n, P[N], mark[N];

vector < pii > tot;

inline void Swp(int i, int j) { swap(P[i], P[j]), tot.push_back(Mp(i, j)); }

void Merge(int x, int y)
{
	while(P[x] ^ y) Swp(x, P[x]);
	while(P[y] ^ x) Swp(y, P[y]);
	Swp(x, y);
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++)
	{
		scanf("%d", &P[i]);
	}
	int x = 0;
	for(int i = 1; i <= n; i ++)
	{
		if(mark[i]) continue;
		int cu = i;
		while(!mark[cu]) 
		{
			mark[cu] = 1;
			cu = P[cu];
		}
		if(i == P[i]) continue;
		if(!x) x = i;
		else 
		{
			Swp(x, i);
			Merge(x, i);
			x = 0;
		}
	}
	if(x)
	{
		/// cycle lenght = 2
		int v1 = 1;
		if(P[P[x]] == x)
		{
			for(v1 = 1; v1 <= 3; v1 ++)
			{
				if(v1 == x || v1 == P[x]) continue;
				break;
			}
			Swp(x, v1);
		}
		else
		{
			v1 = P[x];
			Swp(x, v1);
			Swp(v1, P[x]);
		}
		Merge(x, v1);
	}
	printf("%d\n", SZ(tot));
	for(auto cu : tot)
	{
		printf("%d %d\n", cu.F, cu.S);
	}
    return 0;
}

/** test corner cases(n = 1?) watch for overflow or minus indices **/