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;
int gi() {
	int res = 0, w = 1;
	char ch = getchar();
	while (ch != '-' && !isdigit(ch)) ch = getchar();
	if (ch == '-') w = -1, ch = getchar();
	while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar();
	return res * w;
}
const int MAX_N = 2e5 + 5;
int N, p[MAX_N];
bool vis[MAX_N];
vector<pair<int, int> > ans;
vector<vector<int> > cir;
void Swap(int i, int j) { ans.emplace_back(i, j), swap(p[i], p[j]), p[i] = -p[i], p[j] = -p[j]; }
void doit(vector<int> &v1, vector<int> &v2) {
	int now = v1.size() + v2.size(), p1 = v1[0], p2 = v2[0];
	Swap(p1, p2);
	while (now != 1) {
		if (vis[-p[p1]] && p[-p[p1]] > 0) {
			int t = -p[p1]; vis[t] = 0;
			Swap(p1, t);
		} else if (vis[-p[p2]] && p[-p[p2]] > 0) {
			int t = -p[p2]; vis[t] = 0;
			Swap(p2, t);
		}
		now--;
	}
	Swap(p1, p2);
}
int main () {
#ifndef ONLINE_JUDGE
    freopen("cpp.in", "r", stdin);
#endif
	N = gi();
	for (int i = 1; i <= N; i++) p[i] = gi();
	for (int i = 1; i <= N; i++) {
		if (vis[i]) continue; vector<int> vec;
		for (int o = i; !vis[o]; o = p[o]) vec.push_back(o), vis[o] = 1;
		if (vec.size() > 1) cir.push_back(vec);
	}
	while (cir.size() > 1) {
		vector<int> v1, v2;
		v1 = cir.back(), cir.pop_back(), v2 = cir.back(), cir.pop_back();
		doit(v1, v2);
	}
	if (cir.size()) {
		vector<int> v = cir.back();
		if (v.size() == 2) {
			for (int i = 1; i <= N; i++)
				if (p[i] == i) {
					Swap(v[0], i), Swap(v[1], i), Swap(v[0], i);
					break;
				}
		} else {
			Swap(v[0], v[1]);
			for (int i = 2; i < (int)v.size() - 1; i++) Swap(v[0], v[i]);
			Swap(v.back(), v[1]);
			Swap(v[0], v.back());
			Swap(v[0], v[1]);
		}
	}
	printf("%lu\n", ans.size());
	for (auto it : ans) printf("%d %d\n", it.first, it.second);
    return 0;
}