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 pair<int, int> pii;

int N;
vector<int> V[202020];
int A[202020];
int B[202020];
bool vst[202020];
int id;
vector<pii> ans;

int main() {
	scanf("%d", &N);
	for(int i = 1; i <= N; i++) scanf("%d", &A[i]);
	for(int i = 1; i <= N; i++) {
		if(vst[i]) continue;
		int j = i;
		id++; V[id].push_back(0);
		while(1) {
			vst[j] = true; V[id].push_back(j);
			j = A[j];
			if(j == i) break;
		}
	}

	for(int i = 1; i <= id; i++) B[i] = i;
	sort(B + 1, B + id + 1, [&](const int& a, const int& b) {
		return V[a].size() < V[b].size();
	});

	if(id & 1) {
		int j = B[id];
		if(V[j].size() == 3) {
			int k = B[id - 1];
			ans.emplace_back(V[k][1], V[j][2]);
			ans.emplace_back(V[k][1], V[j][1]);
			ans.emplace_back(V[k][1], V[j][2]);
		}
		else if(V[j].size() > 3) {
			int x = (int)V[j].size() - 1;
			ans.emplace_back(V[j][x - 1], V[j][x]);
			ans.emplace_back(V[j][x - 2], V[j][x]);
			for(int i = 1; i <= x - 2; i++) {
				ans.emplace_back(V[j][i], V[j][x - 1]);
			}
			ans.emplace_back(V[j][x - 1], V[j][x]);
		}
	}

	for(int z = 1; z <= id / 2; z++) {
		int i = B[z * 2 - 1], j = B[z * 2];
		int x = (int)V[i].size() - 1, y = (int)V[j].size() - 1;

		ans.emplace_back(V[i][x], V[j][y]);
		for(int k = 1; k < x; k++) {
			ans.emplace_back(V[i][k], V[j][y]);
		}
		for(int k = 1; k < y; k++) {
			ans.emplace_back(V[i][x], V[j][k]);
		}
		ans.emplace_back(V[i][x], V[j][y]);
	}

	printf("%d\n", ans.size());
	for(auto& i : ans) printf("%d %d\n", i.first, i.second);

	return 0;
}