Madeline has an array $a$ of $n$ integers. A pair $(u, v)$ of integers forms an inversion in $a$ if:

  $1 \le u < v \le n$.  $a_u > a_v$. 

Madeline recently found a magical paper, which allows her to write two indices $u$ and $v$ and swap the values $a_u$ and $a_v$. Being bored, she decided to write a list of pairs $(u_i, v_i)$ with the following conditions:

  all the pairs in the list are distinct and form an inversion in $a$.  all the pairs that form an inversion in $a$ are in the list.  Starting from the given array, if you swap the values at indices $u_1$ and $v_1$, then the values at indices $u_2$ and $v_2$ and so on, then after all pairs are processed, the array $a$ will be sorted in non-decreasing order. 

Construct such a list or determine that no such list exists. If there are multiple possible answers, you may find any of them.


-----Input-----

The first line of the input contains a single integer $n$ ($1 \le n \le 1000$) — the length of the array.

Next line contains $n$ integers $a_1,a_2,...,a_n$ $(1 \le a_i \le 10^9)$  — elements of the array.


-----Output-----

Print -1 if no such list exists. Otherwise in the first line you should print a single integer $m$ ($0 \le m \le \dfrac{n(n-1)}{2}$) — number of pairs in the list.

The $i$-th of the following $m$ lines should contain two integers $u_i, v_i$ ($1 \le u_i < v_i\le n$).

If there are multiple possible answers, you may find any of them.


-----Examples-----
Input
3
3 1 2

Output
2
1 3
1 2

Input
4
1 8 1 6

Output
2
2 4
2 3

Input
5
1 1 1 2 2

Output
0



-----Note-----

In the first sample test case the array will change in this order $[3,1,2] \rightarrow [2,1,3] \rightarrow [1,2,3]$.

In the second sample test case it will be $[1,8,1,6] \rightarrow [1,6,1,8] \rightarrow [1,1,6,8]$.

In the third sample test case the array is already sorted.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
l = list(map(int, input().split()))
order = [(l[i],i) for i in range(n)]
order.sort(reverse = True)

out = []
for v, ind in order:
    for i in range(ind):
        if v < l[i]:
            out.append(str(i + 1)+' '+str(ind + 1))

print(len(out))
print('\n'.join(out))


import sys, math,os
from io import BytesIO, IOBase
#data = BytesIO(os.read(0,os.fstat(0).st_size)).readline
# from bisect import bisect_left as bl, bisect_right as br, insort
# from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
# from decimal import Decimal
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
#sys.setrecursionlimit(100000 + 1)
INF = 10**9
mod = 998244353

step=[(1,0),(-1,0),(0,1),(0,-1)]

n=int(data())
a=mdata()
a1=[]
for i in range(n):
    a1.append((a[i],i))
a1=sorted(a1)
ans=[]
for i in range(n-1,-1,-1):
    k=0
    while a1[k][1]!=i:
        k+=1
    for j in range(k+1,n):
        if a1[k][1]>a1[j][1]:
            a[a1[k][1]],a[a1[j][1]]=a[a1[j][1]],a[a1[k][1]]
            ans.append(str(a1[j][1]+1)+' '+str(a1[k][1]+1))
flag=True
for i in range(n-1):
    if a[i]>a[i+1]:
        flag=False
        break
if flag==True:
    out(len(ans))
    out('\n'.join(ans))
else:
    out(-1)








"""T=int(input())
for _ in range(0,T):
    n=int(input())
    a,b=map(int,input().split())
    s=input()
    s=[int(x) for x in input().split()]
    for i in range(0,len(s)):
        a,b=map(int,input().split())"""




n=int(input())
s=[int(x) for x in input().split()]
kk=[]
for i in range(n):
    h=[]
    kk.append(h)

for i in range(0,len(s)):
    for j in range(i+1,len(s)):
        if(s[i]>s[j]):
            kk[j].append((s[i],i))


for i in range(0,n):
    kk[i].sort()

fnl=[]
for i in range(n-1,-1,-1):
    for j in range(0,len(kk[i])):
        fnl.append((i,kk[i][j][1]))

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


import sys
import math 
from decimal import *
def I(): return int(sys.stdin.readline())
def IL(): return list(map(int,sys.stdin.readline().strip().split()))
def ILS(): return list(map(str,sys.stdin.readline().strip().split()))

def findinv(l):
	p = []
	for i in range(len(l)): 
		for j in range(i+1,len(l)):
			if l[i] > l[j] : p.append((i,-1*l[j],j))
	return p
def check(pp):
	for i in range(1,len(pp)):
		if pp[i]<pp[i-1] : return False
	return True

	

def solve():
	n = I()
	a = IL()
	# inv = findinv(l)
	# if len(inv) == 0 : print(0);return 
	# inv.sort()
	# # print(inv)
	# ll = l.copy()
	# for a,_,b in inv:
	# 	tmp = ll[a]
	# 	ll[a]= ll[b]
	# 	ll[b] = tmp
	# if check(ll) : 
	# 	print(len(inv))
	# 	for a,_,b in inv :
	# 		print(a+1,b+1)
	# 	# print()
	# else : print(-1)
	b=a.copy()

	# for(int i=0;i<n;i++)b[i]=a[i];
	b.sort()
	# sort(b.begin(), b.end());
	inv = []
	for i in range(n):
		inv.append([])
	total = 0
	# v<v<pair<int,int > >>inv(n);
	for i in range(n):
		for j in range(i+1,n):
			if(a[j]<a[i]):
				total+=1;
				inv[i].append([-1*a[j],-1*j]);
			
		
	for i in range(n):
		inv[i].sort()
	for i in range(n):
		for j in range(len(inv[i])):
			# print(inv[i][j])
			inv[i][j][0] *=-1
			inv[i][j][1] *=-1
	for i in range(n):
		for j in range( len(inv[i]) ):
			tmp = a[inv[i][j][1]]
			a[inv[i][j][1]]  = a[i]
			a[i] = tmp
		
	# }
	flag=1 
	for i in range(n): 
		if(b[i]!=a[i]) : flag=0;
	
	if flag == 0 :
		print(-1)
	else :
		print(total)
		for i in range(n):
			for j in range(len(inv[i])):
				print(i+1,inv[i][j][1]+1)
					

solve()

import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def issorted(a):
	for i in range(1,len(a)):
		if a[i-1] > a[i]:
			return False
	return True

def stupid(a,inv,was,order):
	if len(order) == len(inv) and issorted(a):
		return order
	for i in range(len(inv)):
		if was[i] == 0:
			was[i] = 1
			order.append(i)
			x,_,y = inv[i]
			y = -y
			a[x],a[y] = a[y],a[x]
			r = stupid(a,inv,was,order)
			a[x],a[y] = a[y],a[x]
			was[i] = 0
			if r is not None:
				return r
			order.pop()
	return None

#from random import randint

def solve():
	#a = [randint(0,3) for i in range(5)] 
	#print(*a)
	#n = len(a)
	n = mint()
	a = list(mints())
	inv = []
	for i in range(1,n):
		for j in range(i):
			if a[i] < a[j]:
				inv.append((i,-a[j],-j))
	inv.sort(reverse=True)
	#print(inv)
	#r = stupid(a.copy(),inv,[0]*len(inv),[])
	r = list(range(len(inv)))
	#print(*r)
	if r is not None:
		print(len(r))
		for z in r:
			v, _, u = inv[z]
			u = -u
			print(u+1,v+1)
	else:
		print("wut")

#for i in range(mint()):
solve()


n = int(input())
a = list(map(int,input().split()))
aWithIndex = []
for i in range(n):
    aWithIndex.append((a[i],i))
aWithIndex.sort(key = lambda x: x[0])
aOrder = [-1] * n
for i in range(n):
    aOrder[aWithIndex[i][1]] = i
aOrderInverse = [-1] * n
for i in range(n):
    aOrderInverse[aOrder[i]] = i
result = []
for i in range(n):
    for j in range(aOrder[i] - 1, i - 1, -1):
        result.append(str(i + 1) + ' ' + str(aOrderInverse[j] + 1))
        tmp = aOrder[i]
        aOrder[i] = aOrder[aOrderInverse[j]]
        aOrder[aOrderInverse[j]] = tmp
    for j in range(n):
        aOrderInverse[aOrder[j]] = j
print(len(result))
if len(result) != 0:
    print('\n'.join(result))


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def issorted(a):
	for i in range(1,len(a)):
		if a[i-1] > a[i]:
			return False
	return True

def stupid(a,inv,was,order):
	if len(order) == len(inv) and issorted(a):
		return order
	for i in range(len(inv)):
		if was[i] == 0:
			was[i] = 1
			order.append(i)
			x,_,y = inv[i]
			y = -y
			a[x],a[y] = a[y],a[x]
			r = stupid(a,inv,was,order)
			a[x],a[y] = a[y],a[x]
			was[i] = 0
			if r is not None:
				return r
			order.pop()
	return None

n = mint()
a = list(mints())
inv = []
for i in range(1,n):
	for j in range(i):
		if a[i] < a[j]:inv.append((i,-a[j],-j))
inv.sort(reverse=True)
r = list(range(len(inv)))
if r is not None:
	print(len(r))
	for z in r:v, _, u = inv[z];u = -u;print(u+1,v+1)
else:
	print("wut")


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))

def issorted(a):
	for i in range(1,len(a)):
		if a[i-1] > a[i]:
			return False
	return True

n = mint()
a = list(mints())
inv = []
for i in range(1,n):
	for j in range(i):
		if a[i] < a[j]:inv.append((i,-a[j],-j))
inv.sort(reverse=True)
r = list(range(len(inv)))
if r is not None:
	print(len(r))
	for z in r:v, _, u = inv[z];u = -u;print(u+1,v+1)
else:
	print("wut")


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))


n = mint()
a = list(mints())
inv = []
for i in range(1,n):
	for j in range(i):
		if a[i] < a[j]:inv.append((i,-a[j],-j))
inv.sort(reverse=True)
r = list(range(len(inv)))
if r is not None:
	print(len(r))
	for z in r:v, _, u = inv[z];u = -u;print(u+1,v+1)
else:
	print("wut")


import sys

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

def mints():
	return list(map(int, minp().split()))


n = int(input())
a = list(map(int,input().split()))
inv = []
for i in range(1,n):
	for j in range(i):
		if a[i] < a[j]:inv.append((i,-a[j],-j))
inv.sort(reverse=True)
r = list(range(len(inv)))
if r is not None:
	print(len(r))
	for z in r:v, _, u = inv[z];u = -u;print(u+1,v+1)
else:
	print("wut")


n = int(input())
a = list(map(int,input().split()))
inv = []
for i in range(1,n):
	for j in range(i):
		if a[i] < a[j]:inv.append((i,-a[j],-j))
inv.sort(reverse=True)
r = list(range(len(inv)))
if r is not None:
	print(len(r))
	for z in r:v, _, u = inv[z];u = -u;print(u+1,v+1)
else:
	print("wut")


n,a,inv = int(input()),list(map(int,input().split())),[]
for i in range(1,n):
	for j in range(i):
		if a[i] < a[j]:inv.append((i,-a[j],-j))
inv.sort(reverse=True);r = list(range(len(inv)))
if r is not None:
	print(len(r))
	for z in r:v, _, u = inv[z];u = -u;print(u+1,v+1)
else:print("wut")

# from debug import debug
inf = int(1e6)

n = int(input())
lis = list(map(int, input().split()))
store = []
index = list(range(0, n))
for k in range(1, n):
	for _ in range(k):
		for i in range(1, k+1):
			if lis[i] < lis[i-1]:
				lis[i], lis[i-1] = lis[i-1], lis[i]
				index[i], index[i-1] = index[i-1], index[i]
				store.append((index[i]+1, index[i-1]+1))
store.reverse()
print(len(store))
for i in store:
	print(*i)

import sys
input = sys.stdin.readline

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

B=[]
for i in range(n):
    for j in range(i+1,n):
        if A[i]>A[j]:
            B.append((A[i],i+1,j+1))

B.sort()
B.sort(reverse=True,key=lambda x:x[2])

print(len(B))
for x,y,z in B:
    print(y,z)


# Anuneet Anand

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

I = []
for i in range(n):
	for j in range(i+1,n):
		if A[i]>A[j]:
			I.append([A[i],i+1,j+1])

I.sort()
I.sort(key = lambda x:x[2],reverse = True)
print(len(I))
if len(I)>0:
	for i in I:
		j = i[1:]
		print(*j)


# from debug import debug
inf = int(1e6)

n = int(input())
lis = list(map(int, input().split()))
store = []
index = list(range(0, n))
for k in range(1, n):
	for _ in range(k):
		for i in range(1, k+1):
			if lis[i] < lis[i-1]:
				lis[i], lis[i-1] = lis[i-1], lis[i]
				index[i], index[i-1] = index[i-1], index[i]
				store.append((index[i]+1, index[i-1]+1))
store.reverse()
print(len(store))
for i in store:
	print(*i)

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



n = val()
l = li()
l1 = []
for i in range(n):
    for j in range(i + 1,n):
        if l[i] > l[j]:
            l1.append([l[i],i,j])

print(len(l1))
l1.sort()
l1.sort(reverse = 1,key = lambda x:x[-1])
for _,i,j in l1:print(i + 1,j + 1)


n = int(input())
arr = list(map(int, input().split()))
x = []
for i in range(n):
    x.append([arr[i],i])
x.sort(reverse=True)
res = []
for v, pos in x:
    for i in range(pos):
        if arr[i] > v:
            res.append(str(i+1)+' '+str(pos+1))
print(len(res))
print('\n'.join(res))