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: VERY_HARD
Tags: Greedy algorithms

Sorting

Constructive algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
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))


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)


from sys import stdin
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
ans = []
for i in range(n):
	X = a[i]
	now = []
	for j in range(i + 1, n):
		if a[j] < X:
			now.append((a[j], j))
	now.sort()
	now.reverse()
	for (aj, j) in now:
		ans.append((i + 1, j + 1))
print(len(ans))
for i in ans:
	print(*i)


n = int(input())
a = list(map(int, input().split()))
ans = []

def f(l):
	return (-l[1], l[2], l[0])
for i in range(n):
	for j in range(i + 1, n):
		if a[i] > a[j]:
			ans.append((i + 1, j + 1, a[i]))
ans.sort(key=f)
print(len(ans))
for i in ans:
	print(*i[:2])


import sys, io, os
BUFSIZE = 8192

class FastIO(io.IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = io.BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(io.IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
N = int(input())
A = list(map(int, input().split()))
A_ = []
d = {}
for (i, a) in enumerate(A):
	a_ = a * 10000 + i
	A_.append(a_)
A_sorted = sorted(A_)
A_rank = [0] * N
for (i, a_) in enumerate(A_sorted):
	A_rank[a_ % 10000] = i
A = A_rank
Idx = [0] * N
for (i, a) in enumerate(A):
	Idx[a] = i
Ans = []
for a in range(N):
	idx_a = Idx[a]
	for a2 in range(a - 1, -1, -1):
		idx_a2 = Idx[a2]
		if idx_a < idx_a2:
			(A[idx_a], A[idx_a2]) = (A[idx_a2], A[idx_a])
			(Idx[a], Idx[a2]) = (Idx[a2], Idx[a])
			Ans.append((idx_a + 1, idx_a2 + 1))
			a = a2
print(len(Ans))
for ans in Ans:
	print(' '.join(map(str, ans)))


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

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

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

def mints():
	return 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 math, sys, bisect
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
N = int(input())
A = alele()
B = sorted([(A[i], i) for i in range(N)], reverse=True)
Ans = []
for (i, j) in B:
	for k in range(j):
		if i < A[k]:
			Ans.append((k + 1, j + 1))
print(len(Ans))
for (i, j) in Ans:
	print(i, j)


(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')


length = int(input())
arr = [int(x) for x in input().split()]
sorting_by = []
for num in range(length):
	for i in range(num + 1, length):
		if arr[num] > arr[i]:
			sorting_by.append((arr[num], num + 1, i + 1))
sorting_by.sort()
sorting_by.sort(key=lambda x: -x[2])
print(len(sorting_by))
for pair in sorting_by:
	print(pair[1], pair[2])


n = int(input())
arr = [int(i) for i in input().split()]
inversions = []
for i in range(n):
	for j in range(i + 1, n):
		if arr[i] > arr[j]:
			inversions.append((arr[i], i + 1, j + 1))
inversions.sort(key=lambda tup: (-tup[2], tup[0]))
print(len(inversions))
for i in inversions:
	print(i[1], i[2])


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
input = sys.stdin.readline
from collections import defaultdict
n = int(input())
a = [int(i) for i in input().split() if i != '\n']
copy = a[:]
copy.sort()
store = defaultdict(list)
for i in range(n - 1, 0, -1):
	for j in range(i):
		if a[i] < a[j]:
			store[i + 1].append([a[j], j + 1])
	store[i + 1].sort()
ans = []
for i in store:
	ok = False
	last = []
	for j in store[i]:
		ans.append([j[1], i])
print(len(ans))
for i in ans:
	print(*i)


inf = int(1000000.0)
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)


n = int(input())
s = list(map(int, input().split()))
out = []
for i in range(n - 1):
	temp = s[i]
	l = []
	for j in range(i + 1, n):
		if s[j] < temp:
			l.append([s[j], j])
	l.sort()
	l.reverse()
	for ii in l:
		out.append([i, ii[1]])
print(len(out))
for i in out:
	print(i[0] + 1, i[1] + 1)


n = int(input())
a = list(map(int, input().split()))
idx = sorted(range(n), key=lambda i: a[i])
ans = [[] for _ in range(n)]
cnt = 0
for i in range(n):
	for j in range(n - 1, i, -1):
		if a[i] > a[j]:
			ans[i].append(str(i + 1) + ' ' + str(j + 1))
			cnt += 1
print(cnt)
for i in idx:
	if len(ans[i]) == 0:
		continue
	print('\n'.join(ans[i]))


import collections
import bisect
n = int(input())
arr = list(map(int, input().split()))
persuit = sorted(arr)
goal = [0] * n
cnt = collections.defaultdict(int)
for i in range(n):
	index = bisect.bisect_left(persuit, arr[i])
	index += cnt[arr[i]]
	cnt[arr[i]] += 1
	goal[i] = index
indexs = [0] * n
for i in range(n):
	indexs[goal[i]] = i

def is_sort(arr):
	n = len(arr)
	for i in range(n - 1):
		if arr[i + 1] - arr[i] < 0:
			return False
	return True
ans = []
while not is_sort(indexs):
	for i in range(n - 1):
		if indexs[i] > indexs[i + 1]:
			ans.append((indexs[i + 1], indexs[i]))
			(indexs[i], indexs[i + 1]) = (indexs[i + 1], indexs[i])
print(len(ans))
for (u, v) in ans:
	print(u + 1, v + 1)


def swapsort(k, a):
	array_zip = list(zip(a, range(k)))
	array_zip.sort()
	pos = [0 for i in range(k)]
	for i in range(k):
		a[array_zip[i][1]] = i
		pos[i] = array_zip[i][1]
	res = []
	end = False
	while not end:
		end = True
		for i in range(k - 1):
			if pos[i] > pos[i + 1]:
				res.append((pos[i + 1] + 1, pos[i] + 1))
				(pos[i], pos[i + 1]) = (pos[i + 1], pos[i])
				end = False
	print(len(res))
	for t in res:
		print(*t)
k = int(input())
a = [int(s) for s in input().split()]
swapsort(k, a)


import sys, math, cmath, time
start_time = time.time()

def solve():
	n = inp()
	a = inlt()
	q = []
	for i in range(n):
		for j in range(i + 1, n):
			if a[i] > a[j]:
				q.append((a[j], i + 1, j + 1))
	q.sort(reverse=True)
	q.sort(key=lambda x: x[1])
	print(len(q))
	for (x, y, z) in q:
		print(y, z)

def main():
	global tt
	if not ONLINE_JUDGE:
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	t = 1
	for tt in range(t):
		solve()
	if not ONLINE_JUDGE:
		print('Time Elapsed :', time.time() - start_time, 'seconds')
		sys.stdout.close()

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	return input().strip()

def invr():
	return map(int, input().split())

def counter(a, qw):
	q = [0] * qw
	for i in range(len(a)):
		q[a[i] - 1] = q[a[i] - 1] + 1
	return q

def counter_elements(a):
	q = dict()
	for i in range(len(a)):
		if a[i] not in q:
			q[a[i]] = 0
		q[a[i]] = q[a[i]] + 1
	return q

def string_counter(a):
	q = [0] * 26
	for i in range(len(a)):
		q[ord(a[i]) - 97] = (q[ord(a[i]) - 97], 1)
	return q

def factors(n):
	q = []
	for i in range(1, int(n ** 0.5) + 1):
		if n % i == 0:
			q.append(i)
			q.append(n // i)
	return list(sorted(list(set(q))))

def prime_factors(n):
	q = []
	while n % 2 == 0:
		q.append(2)
		n = n // 2
	for i in range(3, int(n ** 0.5) + 1, 2):
		while n % i == 0:
			q.append(i)
			n = n // i
	if n > 2:
		q.append(n)
	return list(sorted(q))

def transpose(a):
	b = [[0] * n for i in range(n)]
	for i in range(len(a)):
		for j in range(len(a)):
			b[i][j] = a[j][i]
	return b
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


input()
a = list(map(int, input().split()))
b = sorted(((i, -a[j], -j) for j in range(len(a)) for i in range(j) if a[i] > a[j]))
print(len(b))
for (i, j, k) in b:
	print(i + 1, -k + 1)


n = int(input())
a = [int(i) for i in input().split()]
ans = 0
dc = [[] for i in range(n)]
for i in range(n):
	for j in range(i):
		if a[i] < a[j]:
			dc[i].append((a[j], j))
			ans += 1
print(ans)
for i in range(n - 1, -1, -1):
	dc[i].sort()
	for j in dc[i]:
		print(j[1] + 1, i + 1)


from os import path
import sys
from heapq import heappush, heappop
from functools import cmp_to_key as ctk
from collections import deque, defaultdict as dd
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from itertools import permutations
from datetime import datetime
from math import ceil, sqrt, log, gcd

def ii():
	return int(input())

def si():
	return input()

def mi():
	return map(int, input().split())

def li():
	return list(mi())
abc = 'abcdefghijklmnopqrstuvwxyz'
mod = 998244353
inf = float('inf')
vow = ['a', 'e', 'i', 'o', 'u']
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def bo(i):
	return ord(i) - ord('a')
file = 1

def solve():
	n = ii()
	a = li()
	b = []
	for (i, x) in enumerate(a):
		b.append([x, i + 1])
	ans = []
	for i in range(n):
		for j in range(n - i - 1):
			if b[j][0] > b[j + 1][0]:
				ans.append([b[j][1], b[j + 1][1]])
				(b[j], b[j + 1]) = (b[j + 1], b[j])
	print(len(ans))
	ans.reverse()
	for i in ans:
		print(*i)
if file:
	if path.exists('input1.txt'):
		sys.stdin = open('input1.txt', 'r')
		sys.stdout = open('output1.txt', 'w')
	else:
		input = sys.stdin.readline
solve()


n = int(input())
arr = list(map(int, input().split()))
ans = []
for i in range(n):
	ans.append((arr[i], i))
ans.sort()
ans = ans[-1::-1]
p = []
for i in ans:
	for j in range(i[1]):
		if i[0] < arr[j]:
			p.append((j + 1, i[1] + 1))
print(len(p))
for i in p:
	print(i[0], i[1])


from sys import stdin, stdout

def main():
	n = int(stdin.readline())
	ary = list(map(int, stdin.readline().split()))
	invs = [[False for i in range(n)] for j in range(n)]
	pair = []
	for i in range(n):
		pair.append((ary[i], i))
	pair.sort()
	perm = [-1] * n
	fxa = [-1] * n
	posof = [-1] * n
	for i in range(n):
		perm[pair[i][1]] = i
		fxa[i] = pair[i][0]
		posof[i] = pair[i][1]
	del pair
	answers = []
	for i in range(n - 1, -1, -1):
		for j in range(perm[i] + 1, n):
			if posof[j] < posof[perm[i]]:
				answers.append(' '.join(map(str, (posof[j] + 1, i + 1))))
	stdout.write(str(len(answers)) + '\n')
	stdout.write('\n'.join(answers))
	return
main()


from heapq import *
import sys
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def solve():
	ai = [(a, i) for (i, a) in enumerate(aa)]
	ai.sort()
	for (na, (a, i)) in enumerate(ai):
		aa[i] = na
	ans = []
	for i in range(n - 1, 0, -1):
		hp = []
		for j in range(i - 1, -1, -1):
			if aa[j] > aa[i]:
				heappush(hp, (aa[j], j))
		while hp:
			(a, j) = heappop(hp)
			aa[j] = aa[i]
			aa[i] = a
			ans.append((j, i))
	print(len(ans))
	for (i, j) in ans:
		print(i + 1, j + 1)
n = II()
aa = LI()
solve()


n = int(input())
a = list(map(int, input().split()))
b = sorted([(a[i], i) for i in range(n)])
res = []
for _ in range(n):
	for i in range(n - 1):
		if b[i][1] > b[i + 1][1]:
			res.append((b[i + 1][1], b[i][1]))
			(b[i], b[i + 1]) = (b[i + 1], b[i])
print(len(res))
for (i, j) in res:
	print(i + 1, j + 1)


length = int(input())
numbers = [int(x) for x in input().split()]
inversions = []
for x in range(length):
	for y in range(x + 1, length):
		if numbers[x] > numbers[y]:
			inversions.append((numbers[x], x + 1, y + 1))
inversions.sort()
inversions.sort(key=lambda tup: -tup[2])
print(len(inversions))
for i in inversions:
	print(i[1], i[2])


import sys, math, os
from io import BytesIO, IOBase
from collections import defaultdict as dd, deque, Counter

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')
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)


import sys

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

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

def mints():
	return 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')


n = int(input())
lst = [int(j) for j in input().split()]
inversions = list()
for i in range(1, n):
	for j in range(i):
		if lst[i] < lst[j]:
			inversions.append((i, -lst[j], -j))
inversions.sort(reverse=True)
res = list(range(len(inversions)))
if res:
	print(len(res))
	for elem in res:
		(v, _, u) = inversions[elem]
		u = -u
		print(u + 1, v + 1)
else:
	print(0)


I = lambda : list(map(int, input().split()))
(n,) = I()
l = I()
ans = []
for i in range(n):
	for j in range(i + 1, n):
		if l[i] > l[j]:
			ans.append([l[i], i + 1, j + 1])
ans.sort()
ans.sort(reverse=True, key=lambda x: x[2])
print(len(ans))
for i in ans:
	print(i[1], i[2])


n = int(input())
arr = list(map(int, input().split()))
brr = []
for i in range(n):
	for j in range(i + 1, n):
		if arr[i] > arr[j]:
			brr.append((arr[i], i + 1, j + 1))
brr.sort()
brr.sort(reverse=True, key=lambda x: x[2])
print(len(brr))
for (a, b, c) in brr:
	print(b, c)


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))


n = int(input())
A = list(map(int, input().split()))
res = []
for i in range(n):
	curr = []
	for j in range(i, n):
		if A[i] > A[j]:
			curr.append([A[j], j])
	curr.sort()
	curr.reverse()
	for inw in curr:
		res.append([i, inw[1]])
print(len(res))
for inw in res:
	print(inw[0] + 1, inw[1] + 1)


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)


from collections import defaultdict

def read_list():
	return list(map(int, input().split(' ')))

def print_list(l):
	print(' '.join(map(str, l)))
n = int(input())
nums = read_list()
res = []
dic = defaultdict(list)
a = list(set(nums))
a.sort()
for i in range(n):
	dic[nums[i]].append(i)
for k in a:
	for i in dic[k]:
		for j in range(n - 1, i, -1):
			if nums[j] < nums[i]:
				res.append('%d %d' % (i + 1, j + 1))
print(len(res))
for s in res:
	print(s)


n = int(input())
li = list(map(int, input().split()))
lp = li.copy()
j = 1
lf = []
c = max(lp)
while j <= n:
	a = min(lp)
	i = lp.index(a)
	li[i] = j
	lp[i] = c + j
	j += 1
while n > 1:
	a = li.pop()
	while a < n:
		i = li.index(a + 1)
		li[i] = a
		lf += [f'{i + 1} {n}']
		a = a + 1
	n -= 1
print(len(lf))
for v in lf:
	print(v)


import sys
inpy = [int(x) for x in sys.stdin.read().split()]
n = inpy[0]
arr = inpy[1:]
res = []
for i in range(n - 1, -1, -1):
	x = []
	for j in range(i):
		if arr[j] > arr[i]:
			x.append((arr[j], j))
	x.sort()
	for (a, j) in x:
		res.append((j + 1, i + 1))
print(len(res))
for (i, j) in res:
	print(i, j)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	n = N()
	arr = RLL()
	res = []
	arrs = sorted([(v, i) for (i, v) in enumerate(arr)], reverse=1)
	for (v, i) in arrs:
		for j in range(i):
			if arr[j] > v:
				res.append([j + 1, i + 1])
	print(len(res))
	for i in res:
		print(*i)
main()


import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
(n,) = I()
l = I()
iv = 0
an = []
pr = [0] * n
ix = [0] * n
for i in range(n):
	c = 0
	for j in range(n):
		if j < i and l[j] == l[i]:
			c += 1
		if l[j] < l[i]:
			c += 1
	pr[i] = c
for i in range(n):
	ix[pr[i]] = i
for i in range(n):
	while pr[i] > i:
		iv += 1
		cr = pr[i] - 1
		an.append([i + 1, ix[cr] + 1])
		d = ix[cr]
		(pr[i], pr[ix[cr]]) = (pr[ix[cr]], pr[i])
		ix[cr + 1] = d
		ix[pr[i]] = i
print(iv)
for i in an:
	print(*i)


import sys

def input():
	return sys.stdin.readline().rstrip()

def split_input():
	return [int(i) for i in input().split()]

def allpos(a):
	n = len(a)
	m = len(a[0])

	def onBoard(i, j):
		return i >= 0 and j >= 0 and (i < n) and (j < m)
	dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
	for i in range(n):
		for j in range(m):
			for d in dirs:
				newi = i + d[0]
				newj = j + d[1]
				if onBoard(newi, newj):
					pass

def isSorted(a):
	for i in range(1, len(a)):
		if a[i] < a[i - 1]:
			return False
	return True
tests = 1
for _ in range(tests):
	n = int(input())
	a = split_input()
	d = {}
	for i in range(len(a)):
		if a[i] not in d:
			d[a[i]] = 1
		else:
			num = d[a[i]] * 0.001
			d[a[i]] += 1
			a[i] += num
	ops = []
	for i in range(n - 1, -1, -1):
		l = []
		for j in range(i):
			if a[j] > a[i]:
				l.append((a[j], j))
		l.sort()
		for elem in l:
			ops.append('%d %d' % (elem[1] + 1, i + 1))
			(a[elem[1]], a[i]) = (a[i], a[elem[1]])
	if isSorted(a):
		print(len(ops))
		print(*ops, sep='\n')
	else:
		print(-1)


import os
import sys
from io import BytesIO, IOBase
import threading
from math import cos, sin, pi

def main():
	for _ in range(1):
		n = int(input())
		arr = list(map(int, input().split()))
		arr = list(zip(arr, range(n)))
		ai = arr.copy()
		ans = []
		for i in range(n - 1, 0, -1):
			can = []
			for j in range(0, i):
				if arr[j] > arr[i]:
					can.append((arr[j], j))
			can.sort()
			prev = arr[i]
			for (val, ind) in can:
				arr[ind] = prev
				prev = val
				ans.append((ind, i))
			arr[i] = prev
	print(len(ans))
	for (i, j) in ans:
		print(i + 1, j + 1)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


it = lambda : list(map(int, input().strip().split()))

def solve():
	N = int(input())
	A = it()
	inversions = []
	for i in range(N):
		inversion = []
		for j in range(i):
			if A[j] > A[i]:
				inversion.append(j)
		inversions.append(inversion)
	R = []
	B = [[a, i] for (i, a) in enumerate(A)]
	for i in range(N - 1, -1, -1):
		inversion = inversions[i]
		inversion.sort(key=lambda x: B[x])
		for j in inversion:
			R.append([j + 1, i + 1])
			(B[i], B[j]) = (B[j], B[i])
	print(len(R))
	for (i, j) in R:
		print(i, j)
solve()


n = int(input())
arr = list(map(int, input().split()))
ans = []
for i in range(n):
	for j in range(n - 1, i, -1):
		if arr[i] > arr[j]:
			ans.append((arr[i], i + 1, j + 1))
ans = sorted(ans, key=lambda x: x[0])
ans = sorted(ans, reverse=True, key=lambda x: x[2])
print(len(ans))
for (_, u, v) in ans:
	print(u, v)


n = int(input())
a = list(map(int, input().split()))
cc = []
for (i, u) in enumerate(a):
	tl = []
	for j in range(n - 1, i, -1):
		if a[j] < u:
			tl.append((i, j))
	cc.append((u, tl))
res = []
for (_, tl) in sorted(cc):
	for (u, v) in tl:
		res.append((u, v))
print(len(res))
for (u, v) in res:
	print(u + 1, v + 1)


import sys

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')

def solve(n, a):
	b = [i for i in range(n)]
	b = sorted(b, key=lambda x: (a[x], x))
	res = []
	for it in range(n):
		for i in range(n - 1):
			if b[i + 1] < b[i]:
				(b[i], b[i + 1]) = (b[i + 1], b[i])
				res.append([b[i] + 1, b[i + 1] + 1])
	wi(len(res))
	for i in range(len(res)):
		wia(res[i])

def main():
	n = ri()
	a = ria()
	solve(n, a)
main()


import sys
from collections import defaultdict as dd
from collections import deque
from fractions import Fraction as f
from copy import *
from bisect import *
from heapq import *
from math import *
from itertools import permutations

def eprint(*args):
	print(*args, file=sys.stderr)
zz = 1
if zz:
	input = sys.stdin.readline
else:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('all.txt', 'w')

def li():
	return [int(x) for x in input().split()]

def fli():
	return [float(x) for x in input().split()]

def gi():
	return [x for x in input().split()]

def fi():
	return int(input())

def swap(a, i, j):
	(a[i], a[j]) = (a[j], a[i])

def si():
	return list(input().rstrip())

def mi():
	return map(int, input().split())

def gh():
	sys.stdout.flush()

def graph(n, m):
	for i in range(m):
		(x, y) = mi()
		a[x].append(y)
		a[y].append(x)

def bo(i):
	return ord(i) - ord('a')
tt = 1
while tt > 0:
	tt -= 1
	n = fi()
	a = li()
	b = [0] * n
	for i in range(n):
		b[i] = [a[i], i]
	b.sort()
	l = deepcopy(a)
	for i in range(n):
		a[i] = b[i][1]
	d = []
	for i in range(n):
		for j in range(n - i - 1):
			if a[j] > a[j + 1]:
				swap(a, j, j + 1)
				swap(l, j, j + 1)
				d.append([a[j] + 1, a[j + 1] + 1])
	print(len(d))
	for i in d:
		print(*i)


from collections import defaultdict
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
sys.setrecursionlimit(10 ** 2)

def print_case_iterable(case_num, iterable):
	print('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))

def print_case_number(case_num, iterable):
	print('Case #{}: {}'.format(case_num, iterable))

def print_iterable(A):
	print(' '.join(A))

def read_int():
	return int(f.readline().strip())

def read_int_array():
	return [int(x) for x in f.readline().strip().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def read_string():
	return list(f.readline().strip())

def ri():
	return int(f.readline().strip())

def ria():
	return [int(x) for x in f.readline().strip().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def rs():
	return list(f.readline().strip())

def bi(x):
	return bin(x)[2:]
from collections import deque
import math
NUMBER = 10 ** 9 + 7

def factorial(n):
	M = NUMBER
	f = 1
	for i in range(1, n + 1):
		f = f * i % M
	return f

def mult(a, b):
	return a * b % NUMBER

def minus(a, b):
	return (a - b) % NUMBER

def plus(a, b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a):
	m = NUMBER
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	if n < k:
		assert false
	return mult(factorial(n), modinv(mult(factorial(k), factorial(n - k)))) % NUMBER
from collections import deque, defaultdict
import heapq
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def dfs(g, timeIn, timeOut, depths, parents):
	cnt = 0
	stack = [[1, 0, 0, 0]]
	while stack:
		(v, neig_i, parent, depth) = stack[-1]
		parents[v] = parent
		depths[v] = depth
		if neig_i == 0:
			timeIn[v] = cnt
			cnt += 1
		while neig_i < len(g[v]):
			u = g[v][neig_i]
			if u == parent:
				neig_i += 1
				continue
			stack[-1][1] = neig_i + 1
			stack.append([u, 0, v, depth + 1])
			break
		if neig_i == len(g[v]):
			stack.pop()
			timeOut[v] = cnt
			cnt += 1
cnt = 0

@bootstrap
def dfs(v, adj, timeIn, timeOut, depths, parents, parent=0, depth=0):
	global cnt
	parents[v] = parent
	depths[v] = depth
	timeIn[v] = cnt
	cnt += 1
	for u in adj[v]:
		if u == parent:
			continue
		yield dfs(u, adj, timeIn, timeOut, depths, parents, v, depth + 1)
	timeOut[v] = cnt
	cnt += 1
	yield

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def get_num_2_5(n):
	twos = 0
	fives = 0
	while n > 0 and n % 2 == 0:
		n //= 2
		twos += 1
	while n > 0 and n % 5 == 0:
		n //= 5
		fives += 1
	return (twos, fives)

def shift(a, i, num):
	for _ in range(num):
		(a[i], a[i + 1], a[i + 2]) = (a[i + 2], a[i], a[i + 1])

def find_mex(a, m):
	b = sorted([x - m for x in a])
	if b[0] > 0:
		return m
	last = 0
	for i in range(len(b)):
		if b[i] > last + 1:
			return last + 1 + m
		last = b[i]
	return b[len(b) - 1] + m + 1

def solution(a, n):
	sol = []
	b = sorted([(a[i], i) for i in range(n)], reverse=True)
	for (x, i) in b:
		for j in range(i):
			if a[j] > a[i]:
				sol.append(f'{j + 1} {i + 1}')
	sol = [f'{len(sol)}'] + sol
	return '\n'.join(sol)

def main():
	T = 1
	for i in range(T):
		n = ri()
		a = ria()
		x = solution(a, n)
		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			(print >> output, str(x))
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()
if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
main()


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()
	b = a.copy()
	b.sort()
	inv = []
	for i in range(n):
		inv.append([])
	total = 0
	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])):
			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()


from sys import stdin, stdout

def inversion_swapsort(n, a):
	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)
	return
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
inversion_swapsort(n, a)


from sys import stdin, stdout

def main():
	n = int(stdin.readline())
	ary = list(map(int, stdin.readline().split()))
	pair = []
	for i in range(n):
		pair.append((ary[i], i))
	pair.sort()
	perm = [-1] * n
	pos = [-1] * n
	for i in range(n):
		perm[pair[i][1]] = i
		pos[i] = pair[i][1]
	del pair
	answers = []
	for i in range(n - 1, -1, -1):
		for j in range(perm[i] + 1, n):
			if pos[j] < pos[perm[i]]:
				answers.append(' '.join(map(str, (pos[j] + 1, i + 1))))
	stdout.write(str(len(answers)) + '\n')
	stdout.write('\n'.join(answers))
	return
main()