You are given a permutation $p$ of integers from $1$ to $n$, where $n$ 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 $i$ and $j$ such that $2 \cdot |i - j| \geq n$ and swap $p_i$ and $p_j$. 

There is no need to minimize the number of operations, however you should use no more than $5 \cdot n$ operations. One can show that it is always possible to do that.


-----Input-----

The first line contains a single integer $n$ ($2 \leq n \leq 3 \cdot 10^5$, $n$ is even) — the length of the permutation. 

The second line contains $n$ distinct integers $p_1, p_2, \ldots, p_n$ ($1 \le p_i \le n$) — the given permutation.


-----Output-----

On the first line print $m$ ($0 \le m \le 5 \cdot n$) — the number of swaps to perform.

Each of the following $m$ lines should contain integers $a_i, b_i$ ($1 \le a_i, b_i \le n$, $|a_i - b_i| \ge \frac{n}{2}$) — 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 $1$ and $2$, 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 $1$ and $5$ the array becomes: $[4, 5, 3, 1, 2, 6]$. After swapping elements on positions $2$ and $5$ the array becomes $[4, 2, 3, 1, 5, 6]$ and finally after swapping elements on positions $1$ and $4$ the array becomes sorted: $[1, 2, 3, 4, 5, 6]$.

Difficulty: interview

Starter code:

Solutions:
# from bisect import bisect_left

# (n) = (int(x) for x in input().split())
n = int(input())
a = [int(_) - 1 for _ in input().split()]

b = [0 for _ in a]
for id, v in enumerate(a):
    b[v] = id

ans = []
for i in range(n):
    pos = b[i]
    target = i
    old_v = a[target]
    if pos == target:
        continue

    # do swap
    b[old_v] = pos
    b[i] = i
    a[target] = i
    a[pos] = old_v


    if (abs(pos - target) * 2 >= n):
        ans.append((pos, target))
        continue
    elif max(pos, target) < n // 2:
        helper = n - 1
        ans.append((pos, helper))
        ans.append((target, helper))
        ans.append((pos, helper))
    elif min(pos, target) >= n // 2:
        helper = 0
        ans.append((pos, helper))
        ans.append((target, helper))
        ans.append((pos, helper))
    else:
        L = 0
        R = n - 1
        if pos > target:
            (pos, target) = (target, pos)
        ans.append((pos, R))
        ans.append((L, R))
        ans.append((L, target))
        ans.append((L, R))
        ans.append((pos, R))

print(len(ans))
for i in ans:
    print(i[0] + 1, i[1] + 1)


input()
p=[int(x)-1 for x in input().split()]
pos=[0] * len(p)
for i, x in enumerate(p):
    pos[x]=i
# print(pos)
ans = []
for i, x in enumerate(p):
    # print('i, x', i, x)
    if i == x:
        continue
    # find x
    i_pos = pos[i]
    # print('i, i_pos', i, i_pos)
    if 2 * abs(i_pos - i) < len(p):
        if 2 * i_pos >= len(p) and 2 * i >= len(p):
            # swap with first
            # print('swap with first')
            ans.append((0, i_pos))
            ans.append((0, i))
            ans.append((0, i_pos))
        elif 2 * ((len(p) - 1) - i_pos) >= len(p) and 2 * ((len(p) - 1) - i) >= len(p):
            # swap with last
            # print('swap with last')
            ans.append((len(p) - 1, i_pos))
            ans.append((len(p) - 1, i))
            ans.append((len(p) - 1, i_pos))
        else:
            # 5 swaps
            # print('5 swaps')
            fi = min(i_pos, i)
            la = max(i_pos, i)
            ans.append((fi, len(p) - 1))
            ans.append((0, len(p) - 1))
            ans.append((0, la))
            ans.append((0, len(p) - 1))
            ans.append((fi, len(p) - 1))
    else:
        ans.append((i, i_pos))
    p[i_pos], p[i] = p[i], p[i_pos]
    pos[p[i_pos]], pos[p[i]] = pos[p[i]], pos[p[i_pos]]
    # print(ans)
print(len(ans))
for a, b in ans:
    print(a+1,b+1)
assert sorted(p) == p


N = int(input())
M = N//2
A = [int(a)-1 for a in input().split()]
B = [0] * (N)
ANS = []
for i in range(N):
    B[A[i]] = i

def calc(i):
    j = B[i]
    if j == i:
        return 0
    if abs(j - i) >= M:
        ANS.append(str(i+1)+" "+str(j+1))
    elif i < M and j < M:
        ANS.append(str(i+1)+" "+str(N))
        ANS.append(str(j+1)+" "+str(N))
        ANS.append(str(i+1)+" "+str(N))
    elif i >= M and j >= M:
        ANS.append(str(1)+" "+str(i+1))
        ANS.append(str(1)+" "+str(j+1))
        ANS.append(str(1)+" "+str(i+1))
    elif i < M:
        ANS.append(str(i+1)+" "+str(N))
        ANS.append(str(1)+" "+str(N))
        ANS.append(str(1)+" "+str(j+1))
        ANS.append(str(1)+" "+str(N))
        ANS.append(str(i+1)+" "+str(N))
    else:
        ANS.append(str(j+1)+" "+str(N))
        ANS.append(str(1)+" "+str(N))
        ANS.append(str(1)+" "+str(i+1))
        ANS.append(str(1)+" "+str(N))
        ANS.append(str(j+1)+" "+str(N))
        
    m = A[i]
    A[i], A[B[i]] = i, A[i]
    B[m] = B[i]
    B[i] = i

for i in range(N):
    calc(i)
print(len(ANS))

print("\n".join(ANS))

n =  int(input())
b = list((list(map(int, input().split()))))

a = list(zip(b,list(range(n))))

a.sort()

a = dict(a)

swaps = []

def swap(i, j):
    if i==j:
        return []
    if 2*(abs(i-j))  >= n:
        return [(i, j)]
    ans = []

    ii  = i
    jj = j
    if i < n//2:
        ans.append((i, n-1))
        ii = n-1
    if j>=n//2:
        ans.append((j, 0))
        jj = 0

    ans.append((ii, jj))

    if i < n//2:
        ans.append((i, n-1))
    if j>=n//2:
        ans.append((j, 0))

    return ans

#print(a)
ans = []
for i in range(n):
    ans.extend(swap(i, a[i+1]))

    t =b[i]
    b[i] = b[a[i+1]]
    b[a[i+1]] = t
    a[t]  = a[i+1]
    a[i+1] =  i
#print(a)
print(len(ans))
for k in ans:
    print(k[0]+1, k[1] +1)


n = int(input())
n2 = n // 2
p = list(map(int, input().split()))
d = [0] * n
for i, v in enumerate(p):
    d[v-1] = i
    
r = []

def sw(i, j):
    r.append((i+1, j+1))

def swap(i, j):
    if i == j:
        pass
    elif abs(i-j) >= n2:
        sw(i,j)
        p[j] = p[i]
    else:
        ti = n-1 if i < n2 else 0
        tj = n-1 if j < n2 else 0
        sw(i, ti)
        if ti != tj: sw(ti, tj)
        sw(tj, j)
        if ti != tj: sw(ti, tj)
        sw(i, ti)
        p[j] = p[i]

for i, v in enumerate(p):
    j = d[i]
    swap(i, j)
    d[v-1] = j

print(len(r))
print("\n".join(f"{a} {b}" for a, b in r))


n=int(input())
a=[0]  + list(map(int,input().split()))
d={}
b=[]
for i in range(1,n+1):
    d[a[i]]=i
m=0    
for i in range(1,n+1):
    ele=a[i]
    if ele!=i and abs(i-d[i])*2>=n:
        m+=1
        b.append([i,d[i]])
        a[i]=i
        a[d[i]]=ele
        d[ele]=d[i]
        d[i]=i
        
        # print("a")
    elif ele!=i and abs(i-d[i])*2<n and i<=n//2 and 2*(d[i]-1)>=n:
        m+=5
        b.append([1,d[i]])
        b.append([1,n])
        b.append([i,n])
        b.append([1,n])
        b.append([1,d[i]])
        a[i]=i
        a[d[i]]=ele
        
        d[ele]=d[i]
        d[i]=i
        # print("b")
    elif ele!=i and abs(i-d[i])*2<n and i<=n//2 and 2*(d[i]-1)<n:
        m+=3
        b.append([n,d[i]])
        b.append([i,n])
        b.append([n,d[i]])
        a[i]=i
        a[d[i]]=ele
        
        d[ele]=d[i]
        d[i]=i
        # print("b")
    
        
    elif ele!=i and abs(i-d[i])*2<n:
        m+=3
        b.append([1,d[i]])
        b.append([i,1])
        b.append([1,d[i]])
        a[i]=i
        a[d[i]]=ele
        d[ele]=d[i]
        d[i]=i
        # print("c")
    # print(d,a)    
print(m)
for i in b:
    print(*i)
        
# print(a)        
        
        
        


n=int(input())
l=list(map(int,input().split()))
ll=[-1]*(n+1)
for i in range(n):
    ll[l[i]]=i
res=[]
#print(ll)
for k in range(1,n+1):
    i=k
    j=ll[k]
    #print(i,j+1)
    if(2*abs((j+1)-i)>=n):
        res.append((i,j+1))
        l[i-1],l[j]=l[j],l[i-1]
        ll[l[i-1]],ll[l[j]]=ll[l[j]],ll[l[i-1]]
    elif(i!=(j+1)):
        if(2*abs(j+1-n)>=n and 2*abs(i-n)>=n):
            res.append((i,n))
            l[i-1],l[n-1]=l[n-1],l[i-1]
            ll[l[i-1]],ll[l[n-1]]=ll[l[n-1]],ll[l[i-1]]
            res.append((j+1,n))
            l[j],l[n-1]=l[n-1],l[j]
            ll[l[j]],ll[l[n-1]]=ll[l[n-1]],ll[l[j]]
            res.append((i,n))
            l[i-1],l[n-1]=l[n-1],l[i-1]
            ll[l[i-1]],ll[l[n-1]]=ll[l[n-1]],ll[l[i-1]]
        elif(2*abs(j+1-1)>=n and 2*abs(i-1)>=n):
            res.append((i,1))
            l[i-1],l[1-1]=l[1-1],l[i-1]
            ll[l[i-1]],ll[l[1-1]]=ll[l[1-1]],ll[l[i-1]]
            res.append((j+1,1))
            l[j],l[1-1]=l[1-1],l[j]
            ll[l[j]],ll[l[1-1]]=ll[l[1-1]],ll[l[j]]
            res.append((i,1))
            l[i-1],l[1-1]=l[1-1],l[i-1]
            ll[l[i-1]],ll[l[1-1]]=ll[l[1-1]],ll[l[i-1]]
        else:
            #print("lol")
            if(i>(j+1)):
                i,j=j+1,i-1
            res.append((i,n))
            l[i-1],l[n-1]=l[n-1],l[i-1]
            ll[l[i-1]],ll[l[n-1]]=ll[l[n-1]],ll[l[i-1]]
            res.append((j+1,1))
            l[j],l[1-1]=l[1-1],l[j]
            ll[l[j]],ll[l[1-1]]=ll[l[1-1]],ll[l[j]]
            res.append((n,1))
            l[n-1],l[1-1]=l[1-1],l[n-1]
            ll[l[n-1]],ll[l[1-1]]=ll[l[1-1]],ll[l[n-1]]
            res.append((i,n))
            l[i-1],l[n-1]=l[n-1],l[i-1]
            ll[l[i-1]],ll[l[n-1]]=ll[l[n-1]],ll[l[i-1]]
            res.append((j+1,1))
            l[j],l[1-1]=l[1-1],l[j]
            ll[l[j]],ll[l[1-1]]=ll[l[1-1]],ll[l[j]]
    #if(l3==l):
        #break
    #print(l,ll,sep="\n")
print(len(res))
for i in res:
    print(i[0],i[1])
#print(l)


n = int(input())
p = list(map(int, input().split()))

ps = p.copy()
ps.sort()
dp = dict()
ds = dict()
for i in range(n):
    if p[i] in dp:
        dp[p[i]] += [i]
    else:
        dp[p[i]] = [i]
        ds[p[i]] = 0

lop = []

for i in range(n):
    if p[i] != ps[i]:
        a = i
        b = dp[ps[i]][ds[ps[i]]]
        if abs(b - a) >= n//2:
            lop.append([a+1, b+1])
        else:
            if a < n//2 and b < n//2:
                bl = [n]
            elif a >= n//2 and b >= n//2:
                bl = [1]
            elif a < n//2:
                bl = [n, 1]
            else:
                bl = [1, n]
            if len(bl) == 2:
                lop.append([a+1, bl[0]])
                lop.append([bl[0], bl[1]])
                lop.append([bl[1], b+1])
                lop.append([bl[0], bl[1]])
                lop.append([a+1, bl[0]])
            else:
                lop.append([a+1, bl[0]])
                lop.append([b+1, bl[0]])
                lop.append([a+1, bl[0]])
        p[a], p[b] = p[b], p[a]
        dp[p[a]][ds[p[a]]], dp[p[b]][ds[p[b]]] = dp[p[b]][ds[p[b]]], dp[p[a]][ds[p[a]]]
    ds[p[i]] += 1

print(len(lop))
for op in lop:
    print(*op)


# from bisect import bisect_left
import sys

# (n) = (int(x) for x in input().split())
n = int(input())
a = [int(_) - 1 for _ in sys.stdin.readline().split()]

b = [0 for _ in a]
for id, v in enumerate(a):
    b[v] = id

ans = []
for i in range(n):
    pos = b[i]
    target = i
    old_v = a[target]
    if pos == target:
        continue

    # do swap
    b[old_v] = pos
    b[i] = i
    a[target] = i
    a[pos] = old_v


    if (abs(pos - target) * 2 >= n):
        ans.append((pos, target))
        continue
    elif max(pos, target) < n // 2:
        helper = n - 1
        ans.append((pos, helper))
        ans.append((target, helper))
        ans.append((pos, helper))
    elif min(pos, target) >= n // 2:
        helper = 0
        ans.append((pos, helper))
        ans.append((target, helper))
        ans.append((pos, helper))
    else:
        L = 0
        R = n - 1
        if pos > target:
            (pos, target) = (target, pos)
        ans.append((pos, R))
        ans.append((L, R))
        ans.append((L, target))
        ans.append((L, R))
        ans.append((pos, R))

print(len(ans))
for i in ans:
    print(i[0] + 1, i[1] + 1)

# from bisect import bisect_left
import sys

# (n) = (int(x) for x in input().split())
n = int(input())
a = [int(_) - 1 for _ in sys.stdin.readline().split()]

b = [0 for _ in a]
for id, v in enumerate(a):
    b[v] = id

ans = []
for i in range(n):
    pos = b[i]
    target = i
    old_v = a[target]
    if pos == target:
        continue

    # do swap
    b[old_v] = pos
    b[i] = i
    a[target] = i
    a[pos] = old_v


    if (abs(pos - target) * 2 >= n):
        ans.append((pos, target))
        continue
    elif max(pos, target) < n // 2:
        helper = n - 1
        ans.append((pos, helper))
        ans.append((target, helper))
        ans.append((pos, helper))
    elif min(pos, target) >= n // 2:
        helper = 0
        ans.append((pos, helper))
        ans.append((target, helper))
        ans.append((pos, helper))
    else:
        L = 0
        R = n - 1
        if pos > target:
            (pos, target) = (target, pos)
        ans.append((pos, R))
        ans.append((L, R))
        ans.append((L, target))
        ans.append((L, R))
        ans.append((pos, R))

print(len(ans))
print("\n".join(f"{i[0] + 1} {i[1] + 1}" for i in ans))
# for i in ans:
#     print(i[0] + 1, i[1] + 1)