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 <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define dingyi int mid = l + r >> 1, ls = p << 1, rs = p << 1 | 1
#define y0 y_csyakioi_0
#define y1 y_csyakioi_1
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define per(i, x, y) for(int i = x; i <= y; --i)
#define repg(i, u) for(int i = head[u]; i; i = e[i].nxt)
inline int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
	while(ch >= '0' && ch <= '9'){ x = x * 10 + (ch ^ 48); ch = getchar(); }
	return x * f;
}
const int N = 200010;
int n, len, x, y, z, a[N], ans[N][2]; bool vis[N], flag;
inline void Move(int x, int y){
	ans[++len][0] = x; ans[len][1] = y;
	swap(a[x], a[y]); a[x] = -a[x]; a[y] = -a[y];
}
inline void Swap(int x, int y){
	Move(x, y); int z = x;
	while(a[-a[z]] > 0) Move(z, -a[z]); z = -a[z];
	while(a[-a[z]] > 0) Move(z, -a[z]); Move(z, -a[z]);
}
inline void mian(){
	n = read(); rep(i, 1, n) a[i] = read(); x = -1;
	rep(i, 1, n){
		if(!vis[i]){
			if(a[i] == i) continue;
			y = i; vis[y] = 1; y = a[y];
			while(y != i) vis[y] = 1, y = a[y];
			if(x == -1) x = i;
			else Swap(x, i), x = -1;
		}
	}
	if(x != -1){
		rep(i, 1, n) if(a[i] == i){ Swap(x, i); flag = 1; break; }
		if(!flag){
			y = a[x]; z = a[y];
			Move(x, y); Swap(y, z); 
		}
	}
	printf("%d\n", len); rep(i, 1, len) printf("%d %d\n", ans[i][0], ans[i][1]);
}
int main(){ int qwq = 1; while(qwq--) mian(); return 0; }