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;

const int N = 200000 + 10;

int n, a[N], _a[N];
int nxt[N], vis[N];
vector <pair<int, int>> ans;

void Ans(int pos1, int pos2) {
	ans.push_back({pos1, pos2});
	swap(a[pos1], a[pos2]);
	swap(nxt[pos1], nxt[pos2]);
	a[pos1] = -a[pos1];
	a[pos2] = -a[pos2];
	// cout << "swap ";
	// cout << pos1 << ' ' << pos2 << '\n';
	// for (int j = 1; j <= n; j++) {
	// 	cout << a[j] << ' ';
	// } cout << '\n';
	// for (int j = 1; j <= n; j++) {
	// 	cout << nxt[j] << ' ';
	// } cout << '\n';
	// memset(vis, 0, sizeof(vis));
	// for (int i = 1; i <= n; i++) {
	// 	if (vis[i])	continue;
	// 	vector <int> _;
	// 	for (int j = i; !vis[j]; j = abs(a[j])) {
	// 		_.push_back(j);
	// 		vis[j] = 1;
	// 	}
	// 	if (_.size() == 1)	continue;
	// 	for (auto x : _) {
	// 		cout << x << " -> ";
	// 	} cout << '\n';
	// }
}

void Out() {
	if (ans.size() > n + 1)	puts("No 1");
	for (int i = 1; i <= n; i++) {
		// assert(a[i] == i);
		if (a[i] != i) {
			printf("No 2 %d %d %d\n", i, a[i], _a[i]);
		}
	}
	printf("%d\n", ans.size());
	for (auto [pos1, pos2] : ans) {
		printf("%d %d\n", pos1, pos2);
	}
}

void Work2(vector <int> &b) {
	vector <int> c;
	for (auto x : b) {
		if (a[x] < 0) {
			c.push_back(x);
		}
	}
	while (true) {
		int pos1 = abs(c[0]), pos2 = abs(a[pos1]);
		if (a[pos1] < 0 && a[pos2] < 0) {
			pos1 = abs(c[1]), pos2 = abs(a[pos1]);
			if (a[pos1] < 0 && a[pos2] < 0) {
				Ans(pos1, pos2);
				break;
			}
		}
		Ans(pos1, pos2);
	}
}

void Work1(vector <int> &b) {
	if (b.size() == 1)	return;
	int pos1 = a[b[0]], pos2 = a[pos1];
	Ans(pos1, pos2);
	for (auto x : b) {
		if (a[x] > 0) {
			Ans(x, pos2);
			break;
		}
	}
	Work2(b);
}

void Solve() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)	scanf("%d", &a[i]);
	bool flag = true;
	for (int i = 1; i <= n; i++) {
		_a[i] = a[i];
		if (a[i] != i) {
			flag = false;
		}
	}
	if (flag) {
		Out();
		return;
	}
	vector <vector <int>> _v, __v;
	for (int i = 1; i <= n; i++) {
		if (vis[i])	continue;
		vector <int> _;
		for (int j = a[i]; !vis[j]; j = a[j]) {
			_.push_back(j);
			vis[j] = 1;
			nxt[j] = a[j];
		}
		if (_.size() == 1) {
			__v.push_back(_);
		}
		else	_v.push_back(_);
	}
	for (auto _ : __v) {
		_v.push_back(_);
		break;
	}
	if (_v.size() == 1) {
		Work1(_v[0]);
		_v.pop_back();
	}
	for (int i = 0; i < _v.size(); i += 2) {
		if (_v[i].size() == 1 && _v[i + 1].size() == 1)	continue;
		int pos1 = _v[i][0], pos2 = _v[i + 1][0];
		Ans(pos1, pos2);
		if (i + 3 == _v.size()) {
			int pos1 = _v[i][0], pos2 = _v[i + 2][0];
			Ans(pos1, pos2);
			i++;
		}
		vector <int> _;
		int now = _v[i][0];
		_.push_back(now);
		while (nxt[now] != _[0]) {
			now = nxt[now];
			_.push_back(now);
		}
		Work2(_);
	}

	Out();
}

int main(){
    srand(time(0));
#ifndef ONLINE_JUDGE
    freopen("data.in", "r", stdin);
    freopen("tst.out", "w", stdout);
    clock_t st = clock();
#endif
    int T = 1;
    while (T--) {
		Solve();
    }
#ifndef ONLINE_JUDGE
    clock_t ed = clock();
    // printf("time : %.6lfs\n", 1.0 * (ed - st) / CLOCKS_PER_SEC);
#endif
    return 0;
}