You are given a permutation pp of integers from 11 to nn, where nn is an even number.

Your goal is to sort the permutation. To do so, you can perform zero or more operations of the following type:

take two indices ii and jj such that 2?|i?j|≥n2?|i?j|≥n and swap pipi and pjpj.
There is no need to minimize the number of operations, however you should use no more than 5?n5?n operations. One can show that it is always possible to do that.

Input
The first line contains a single integer nn (2≤n≤3?1052≤n≤3?105, nn is even) — the length of the permutation.

The second line contains nn distinct integers p1,p2,…,pnp1,p2,…,pn (1≤pi≤n1≤pi≤n) — the given permutation.

Output
On the first line print mm (0≤m≤5?n0≤m≤5?n) — the number of swaps to perform.

Each of the following mm lines should contain integers ai,biai,bi (1≤ai,bi≤n1≤ai,bi≤n, |ai?bi|≥n2|ai?bi|≥n2) — the indices that should be swapped in the corresponding swap.

Note that there is no need to minimize the number of operations. We can show that an answer always exists.

Examples
Input
2
2 1
Output
1
1 2
Input
4
3 4 1 2
Output
4
1 4
1 4
1 3
2 4
Input
6
2 5 3 1 4 6
Output
3
1 5
2 5
1 4
Note
In the first example, when one swap elements on positions 11 and 22, the array becomes sorted.

In the second example, pay attention that there is no need to minimize number of swaps.

In the third example, after swapping elements on positions 11 and 55 the array becomes: [4,5,3,1,2,6][4,5,3,1,2,6]. After swapping elements on positions 22 and 55 the array becomes [4,2,3,1,5,6][4,2,3,1,5,6] and finally after swapping elements on positions 11 and 44 the array becomes sorted: [1,2,3,4,5,6][1,2,3,4,5,6].
題意：給你一組序列，要你還原成1，2，3，，，n的序列，每一次交換需要這樣做：對于i來說，和它交換的j需要滿足2?|i?j|≥n.
思路：這個題一開始毫無思路，我知道給定的交換條件2?|i?j|≥n和最多不會超過5*n肯定是有原因的，但是沒搞懂。。。看了題解之后明白了，對于一個想交換到另一半的數(shù)字，我們可以先與1或者n交換，然后再交換到相應的位置，這樣的話，就能夠保證交換的時候肯定是滿足2?|i?j|≥n的了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=3e5+100; int a[maxx]; int pos[maxx]; struct node{int x,y; }p[maxx*5+100]; int n,cnt;inline void judge(int x,int y) {p[++cnt].x=x;p[cnt].y=y;swap(a[x],a[y]);pos[a[x]]=x,pos[a[y]]=y; } int main() {scanf("%d",&n);cnt=0;for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;int i;for(i=2;i<=n/2;i++){if(pos[i]<=n/2){judge(pos[i],n);judge(n,i);}else{judge(pos[i],1);judge(1,n);judge(i,n);}}for(;i<n;i++){if(pos[i]<=n/2){judge(pos[i],n);judge(1,n);judge(1,i);}else{judge(pos[i],1);judge(1,i);}}if(a[1]!=1) judge(1,n);cout<<cnt<<endl;for(int i=1;i<=cnt;i++) cout<<p[i].x<<" "<<p[i].y<<endl; }

努力加油a啊，(^o)/~

總結(jié)

以上是生活随笔為你收集整理的Crazy Diamond CodeForces - 1148C（思维构造）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。