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 <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <deque>
#include <cmath>
#include <math.h>
#include <string>
#include <time.h>
#include <random>
#include <memory.h>
#include <bitset>
using namespace std;

#define FILE0
#define MAGIC0
mt19937 rnd(time(0)); //rnd()

#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mii map<int, int>
#define mll map<ll, ll>
#define msl map<string, ll>
#define mls map<ll, string>
#define MOD (1000000007ll)
#define MOD2 (1000000009ll)
#define BIGMOD (1000000000000000007ll)
#define RMOD int(5e8 + rnd() % (int) 5e8)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#ifdef FILE1
ifstream in("input.txt");
ofstream out("output.txt");
#endif
#ifdef MAGIC1
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

bool isPrime(ll a)
{
	ll i;
	for (i = 2; i*i <= a; i++)
	{
		if (a%i == 0)
		{
			return 0;
		}
	}
	return (a != 1);
}

bool isPalindrom(const string &s, int l, int r)
{
	for (int i = 0; i < (r - l + 1) / 2; i++)
	{
		if (s[l + i] != s[r - i])
		{
			return 0;
		}
	}
	return 1;
}

template <class type1> type1 gcd(type1 a, type1 b)
{
	type1 t;
	while (b)
	{
		t = b;
		b = a%b;
		a = t;
	}
	return a;
}

ll positiveMod(ll v, ll md)
{
	v = v%md;
	if (v < 0)
	{
		v += md;
	}
	return v;
}

//-----------------------------------------------------end--------------------------------------//

vector <int> dat;
vector <int> type;
vector <int> pos;

vector <pii> res;

vector <int> used;
vector <vector <int> > cycles;

void ss(vector <int> c1, vector <int> c2)
{
	reverse(c1.begin() + 1, c1.end());
	reverse(c2.begin() + 1, c2.end());

	res.push_back({ c1[0], c2[1] });
	res.push_back({ c2[0], c1[1] });

	for (int i = c2.size() - 1; i > 1; i--)
	{
		res.push_back({ c1[1], c2[i] });
	}
	for (int i = c1.size() - 1; i > 1; i--)
	{
		res.push_back({ c2[1], c1[i] });
	}

	res.push_back({ c1[0], c2[0] });
	res.push_back({ c1[1], c2[1] });
}

int main()
{
	fast;
	
	int n, i, a;

	cin >> n;
	pos.resize(n + 1), 0;
	used.resize(n + 1, 0);
	
	dat.push_back(0);
	type.push_back(0);
	for (i = 1; i <= n; i++)
	{
		cin >> a;

		dat.push_back(a);
		type.push_back(0);
		pos[a] = i;
	}

	for (int i = 1; i < n; i++)
	{
		if (used[i] == 0)
		{
			vector <int> cyc;

			cyc.push_back(i);

			a = dat[i];
			used[i] = 1;
			while (a != i)
			{
				cyc.push_back(a);
				used[a] = 1;

				a = dat[a];
			}

			if (cyc.size() != 1)
			{
				cycles.push_back(cyc);
			}
		}
	}

	while (cycles.size() > 1)
	{
		vector <int> c1 = cycles.back();
		cycles.pop_back();
		vector <int> c2 = cycles.back();
		cycles.pop_back();

		ss(c1, c2);
	}

	if (cycles.size() != 0)
	{
		vector <int> c = cycles[0];

		if (c.size() == 2)
		{
			int outer;

			for (outer = 1; outer <= n; outer++)
			{
				if (outer != c[0] && outer != c[1])
				{
					break;
				}
			}

			res.push_back({ c[0], outer });
			res.push_back({ c[1], outer });
			res.push_back({ c[0], outer });
		}
		else if (c.size() == 3)
		{
			res.push_back({ c[0], c[1] });
			res.push_back({ c[1], c[2] });
			res.push_back({ c[0], c[2] });
			res.push_back({ c[0], c[1] });
		}
		else
		{
			reverse(c.begin() + 1, c.end());

			int sz = c.size();

			for (int i = sz - 1; i > 1; i--)
			{
				res.push_back({ c[0], c[i] });
			}
			res.push_back({ c[1], c[sz - 1] });
			res.push_back({ c[0], c[1] });
			res.push_back({ c[0], c[sz - 1] });
		}
	}

	cout << res.size() << "\n";
	for (auto it : res)
	{
		cout << it.first << " " << it.second << "\n";
	}

	/*
	cout << "\n\n";

	for (auto it : res)
	{
		swap(dat[it.first], dat[it.second]);
		dat[it.second] *= -1;
		dat[it.second] *= -1;
	}
	for (i = 1; i <= n; i++)
	{
		cout << dat[i] << " ";
	}
	cout << "\n";
	*/

	return 0;
}