In a previous challenge you implemented the Insertion Sort algorithm. It is a simple sorting algorithm that works well with small or mostly sorted data. However, it takes a long time to sort large unsorted data. To see why, we will analyze its running time.

Running Time of Algorithms 

The running time of an algorithm for a specific input depends on the number of operations executed. The greater the number of operations, the longer the running time of an algorithm. We usually want to know how many operations an algorithm will execute in proportion to the size of its input, which we will call $unrecognized$.

What is the ratio of the running time of Insertion Sort to the size of the input? To answer this question, we need to examine the algorithm. 

Analysis of Insertion Sort 

For each element $unrecognized$ in an array of $unrecognized$ numbers, Insertion Sort compares the number to those to its left until it reaches a lower value element or the start.  At that point it shifts everything to the right up one and inserts $unrecognized$ into the array. 

How long does all that shifting take?

In the best case, where the array was already sorted, no element will need to be moved, so the algorithm will just run through the array once and return the sorted array. The running time would be directly proportional to the size of the input, so we can say it will take $unrecognized$ time.

However, we usually focus on the worst-case running time (computer scientists are pretty pessimistic). The worst case for Insertion Sort occurs when the array is in reverse order. To insert each number, the algorithm will have to shift over that number to the beginning of the array. Sorting the entire array of $unrecognized$ numbers will therefore take $unrecognized$ operations, which is $unrecognized$ (almost $unrecognized$$unrecognized$$unrecognized$). Computer scientists just round that up (pick the dominant term) to $unrecognized$$unrecognized$ and say that Insertion Sort is an "$unrecognized$$unrecognized$ time" algorithm.

What this means 

The running time of the algorithm against an array of $unrecognized$ elements is $unrecognized$$unrecognized$. For $unrecognized$ elements, it will be $unrecognized$$unrecognized$.  Insertion Sort can work well for small inputs or if you know the data is likely to be nearly sorted, like check numbers as they are received by a bank.  The running time becomes unreasonable for larger inputs. 

Challenge 

Can you modify your previous Insertion Sort implementation to keep track of the number of shifts it makes while sorting? The only thing you should print is the number of shifts made by the algorithm to completely sort the array. A shift occurs when an element's position changes in the array. Do not shift an element if it is not necessary.

Function Description

Complete the runningTime function in the editor below.   

runningTime has the following parameter(s):  

int arr[n]: an array of integers   

Returns   

int: the number of shifts it will take to sort the array   

Input Format

The first line contains the integer $unrecognized$, the number of elements to be sorted. 

The next line contains $unrecognized$ integers of $unrecognized$. 

Constraints

$unrecognized$ 

$unrecognized$

Sample Input
STDIN       Function
-----       --------
5           arr[] size n =5
2 1 3 1 2   arr = [2, 1, 3, 1, 2]

Sample Output
4

Explanation
Iteration   Array      Shifts
0           2 1 3 1 2
1           1 2 3 1 2     1
2           1 2 3 1 2     0
3           1 1 2 3 2     2
4           1 1 2 2 3     1

Total                     4

Difficulty: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
size = int(input())
array = input().split(' ')
arr = ['None'] * size
for i in range(size):
	arr[i] = int(array[i])
i = 1
count = 0
while i < size:
	tmp = arr[i]
	j = i - 1
	while arr[j] > tmp and j > -1:
		arr[j + 1] = arr[j]
		j = j - 1
		count = count + 1
	arr[j + 1] = tmp
	i = i + 1
print(count)


n = int(input())
line = list(map(int, input().split()))
shifts = 0

def list_print(lst):
	print(' '.join(map(str, lst)))

def insert(lst, i):
	pos = i - 1
	shifts = 0
	for pos in range(i - 1, -1, -1):
		if lst[pos] > lst[pos + 1]:
			(lst[pos], lst[pos + 1]) = (lst[pos + 1], lst[pos])
			shifts += 1
	return shifts
for stop in range(1, n):
	shifts += insert(line, stop)
print(shifts)


s = int(input())
input_ar = input().split()
ar = [int(x) for x in input_ar]
shift_count = 0
for i in range(1, s):
	j = i - 1
	if ar[i] >= ar[j]:
		continue
	v = ar[i]
	while v < ar[j] and j >= 0:
		ar[j + 1] = ar[j]
		shift_count += 1
		j -= 1
	ar[j + 1] = v
print(shift_count)


n = int(input())
d = [int(x) for x in input().split()]
s = 0
i = 1
while i < n:
	k = i
	while k > 0 and d[k] < d[k - 1]:
		(d[k], d[k - 1]) = (d[k - 1], d[k])
		k -= 1
		s += 1
	i += 1
print(s)


import sys
count = None
a_list = None
for line in sys.stdin:
	if count is None:
		count = int(line.strip())
		continue
	a_list = [int(i) for i in line.strip().split(' ')]
shift_count = 0
for i in range(1, count):
	V = a_list[i]
	for j in range(i):
		if V < a_list[i - j - 1]:
			tmp = a_list[i - j - 1]
			a_list[i - j - 1] = V
			a_list[i - j] = tmp
			shift_count += 1
print(shift_count)


import sys

def insertionSort(ar):
	if len(ar) <= 1:
		return 0
	i = 1
	count = 0
	for i in range(len(ar)):
		toInsert = ar[i]
		insertLocation = i
		while insertLocation > 0 and int(toInsert) < int(ar[insertLocation - 1]):
			if int(ar[insertLocation]) != int(ar[insertLocation - 1]):
				ar[insertLocation] = ar[insertLocation - 1]
				count += 1
			insertLocation -= 1
		ar[insertLocation] = toInsert
	return count
length = int(sys.stdin.readline().strip())
smth = sys.stdin.readline().strip().split(' ')
print(insertionSort(smth[0:length]))


def insert(ar):
	u = ar.pop()
	k = 0
	for i in range(len(ar) - 1, -1, -1):
		if ar[i] <= u:
			ar.insert(i + 1, u)
			return (ar, k)
		k += 1
	ar.insert(0, u)
	return (ar, k)

def insertionSort(ar):
	k = 0
	for i in range(2, len(ar) + 1):
		(ar[0:i], i) = insert(ar[0:i])
		k += i
	print(k)
m = int(input())
ar = [int(i) for i in input().strip().split()]
if m == 1:
	0
elif m == len(ar):
	insertionSort(ar)


def insertionSort(m, ar):
	shift = 0
	if m < 2:
		print(shift)
	else:
		for index in range(1, m):
			while ar[index] < ar[index - 1]:
				(ar[index], ar[index - 1]) = (ar[index - 1], ar[index])
				shift += 1
				if index > 1:
					index -= 1
		print(shift)
m = int(input())
ar = [int(i) for i in input().strip().split()]
insertionSort(m, ar)


def insertionSort2(ar):
	s = len(ar) - 2
	check = int(ar[-1])
	shift_count = 0
	for x in range(s, -1, -1):
		if int(ar[x]) <= check:
			ar[x + 1] = str(check)
			break
		else:
			ar[x + 1] = ar[x]
			shift_count += 1
			if x == 0:
				ar[0] = str(check)
	return (ar, shift_count)
s = input()
ar = input()
ar = ar.split()
shift_count = 0
for x in range(2, len(ar) + 1):
	ar_in_so = insertionSort2(ar[:x])
	shift_count += ar_in_so[1]
	ar_check = ar_in_so[0]
	ar_rest = ar[x:]
	ar = ar_check + ar_rest
print(shift_count)


x = int(input())
a = input().split()
count = 0
if x == 1:
	print(a[0])
j = 1
while j < x:
	i = j
	v = int(a[i])
	while i > 0:
		t1 = int(a[i - 1])
		if t1 > v:
			a[i] = t1
			a[i - 1] = v
			count += 1
		i -= 1
	j += 1
print(count)


l = int(input())
ar = input().split()
for size in range(l):
	ar[size] = int(ar[size])

def shift(plist, index):
	temp = plist[index]
	if plist[index - 1] > plist[index]:
		plist[index] = plist[index - 1]
		plist[index - 1] = temp
		if hasattr(shift, 'count'):
			shift.count += 1
		else:
			shift.count = 1
		if index - 2 == -1:
			pass
		else:
			shift(plist, index - 1)
	return plist
for listing in range(1, l):
	string = ''
	ar = shift(ar, listing)
if hasattr(shift, 'count'):
	print(shift.count)
else:
	print(0)


def sort(li, i):
	shift = 0
	j = i - 1
	while j >= 0:
		if li[j] <= li[i]:
			break
		help = li[i]
		li[i] = li[j]
		li[j] = help
		shift += 1
		i -= 1
		j -= 1
	return shift
shift = 0
n = int(input())
array = [int(x) for x in input().split()]
for i in range(1, n):
	shift += sort(array, i)
print(shift)


def insert(ar, index):
	while index > 0:
		if ar[index - 1] > ar[index]:
			tmp = ar[index]
			ar[index] = ar[index - 1]
			ar[index - 1] = tmp
			index = index - 1
			ar[-1] = ar[-1] + 1
		else:
			return ar
	return ar

def insertionSort(ar):
	shifts = 0
	length = len(ar)
	ar.append(shifts)
	for i in range(length - 1):
		ar = insert(ar, i + 1)
	return ar[-1]
num = [int(i) for i in input().strip().split()]
ar = [int(j) for j in input().strip().split()]
print(insertionSort(ar))


import sys

def print_ar(a):
	for i in a:
		print(i, end=' ')
	print('')

def insert_key(n, ar):
	shift_count = 0
	key = ar[n - 1]
	k = n - 1
	for i in range(n - 2, -1, -1):
		if key < ar[i]:
			ar[i + 1] = ar[i]
			shift_count = shift_count + 1
			k = k - 1
		else:
			break
	ar[k] = key
	return shift_count
n = int(sys.stdin.readline())
raw = sys.stdin.readline().split()
ar = []
total_count = 0
for i in raw:
	ar.append(int(i))
if n < 2:
	print_ar(ar)
else:
	for i in range(2, n + 1):
		total_count = total_count + insert_key(i, ar)
print(total_count)


def insertionSort1(arr):
	length = len(arr)
	count = 0
	v = arr[length - 1]
	for i in range(length - 2, -1, -1):
		if arr[i] > v:
			count += 1
			arr[i + 1] = arr[i]
		else:
			arr[i + 1] = v
			break
	if arr[0] > v:
		arr[0] = v
	return [arr, count]

def insertionSort(arr):
	length = len(arr)
	count = 0
	for i in range(1, length):
		if arr[i] < arr[i - 1]:
			[arr[:i + 1], tempCount] = insertionSort1(arr[:i + 1])
			count += tempCount
	print(count)
m = int(input())
arr = []
tempStr = input().strip().split()
for i in range(0, m):
	arr.append(int(tempStr[i]))
insertionSort(arr)


import sys

def insertionSort(ar):
	shift = 0
	if len(ar) > 1:
		for i in range(1, len(ar)):
			if ar[i - 1] > ar[i]:
				e = int(len(ar[0:i + 1])) - 1
				newNum = ar[e]
				done = False
				while done == False:
					if ar[e - 1] > newNum:
						ar[e] = ar[e - 1]
						e -= 1
						shift += 1
						done = e == 0
					else:
						done = True
				ar[e] = newNum
	sys.stdout.write(str(shift))
	return ar

def buildString(ar):
	string = str(' ')
	for i in range(len(ar)):
		string += str(ar[i]) + ' '
	sys.stdout.write(string.strip() + '\n')
	return string

def main():
	m = int(input())
	i = int(0)
	ar = list()
	ar = [int(i) for i in input().strip().split()]
	insertionSort(ar)
	return 0
main()


import sys

def insertion_sort(ar):
	if len(ar) <= 1:
		print(0)
		return ar
	else:
		shifts = 0
		for j in range(1, len(ar)):
			for i in reversed(range(j)):
				if ar[i + 1] < ar[i]:
					(ar[i], ar[i + 1]) = (ar[i + 1], ar[i])
					shifts += 1
				else:
					break
		print(shifts)
		return ar
s = int(sys.stdin.readline())
ar = list(map(int, sys.stdin.readline().split()))
insertion_sort(ar)


import copy

class Bit:

	def __init__(self, n):
		sz = 1
		while n >= sz:
			sz *= 2
		self.size = sz
		self.data = [0] * sz

	def sum(self, i):
		assert i > 0
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		assert i > 0
		while i < self.size:
			self.data[i] += x
			i += i & -i

def maxValue(ar):
	max = 0
	for i in ar:
		if i > max:
			max = i
			continue
	return max

def inversions(arToCountShift):
	res = 0
	bit = Bit(maxValue(arToCountShift))
	for (i, v) in enumerate(arToCountShift):
		res += i - bit.sum(v)
		bit.add(v, 1)
	return res

def printArrayAsString(arToPrint):
	arStringInt = []
	for i in arToPrint:
		arStringInt.append(str(i))
	print(' '.join(arStringInt))

def insertSort(arIntToSort):
	numOcurence = 0
	for index in range(1, len(arIntToSort)):
		valueToInsert = arIntToSort[index]
		holePos = index
		while holePos > 0 and valueToInsert < arIntToSort[holePos - 1]:
			arIntToSort[holePos] = arIntToSort[holePos - 1]
			holePos = holePos - 1
			numOcurence = numOcurence + 1
		arIntToSort[holePos] = valueToInsert
	return numOcurence

def main():
	strNumTestCase = input()
	intNumTestCase = int(strNumTestCase)
	for i in range(intNumTestCase):
		strLengthArray = input()
		intLengthArray = int(strLengthArray)
		strValidArray = input()
		arStringValidArray = strValidArray.split()
		arIntValidArray = []
		for val in arStringValidArray:
			arIntValidArray.append(int(val))
		print(inversions(arIntValidArray))

def main2():
	strLengthArray = input()
	intLengthArray = int(strLengthArray)
	strValidArray = input()
	arStringValidArray = strValidArray.split()
	arIntValidArray = []
	for val in arStringValidArray:
		arIntValidArray.append(int(val))
	print(insertSort(arIntValidArray))
main2()


def start():
	s = int(input())
	text = input().split(' ')
	a = []
	for i in range(s):
		a.append(int(text[i]))
	return a

def insertionSortCount(a):
	count = 0
	for i in range(1, len(a)):
		v = a[i]
		j = i - 1
		while j >= 0:
			if a[j] > v:
				a[j + 1] = a[j]
				a[j] = v
				count += 1
			j -= 1
	return count
print(insertionSortCount(start()))


size = int(input())
arr = input().strip().split()
arr = [int(entry) for entry in arr]
shifts = 0
for i in range(1, size):
	key = arr[i]
	j = i - 1
	while j >= 0 and arr[j] > key:
		arr[j + 1] = arr[j]
		j -= 1
		shifts += 1
	arr[j + 1] = key
print(shifts)


import sys

def insertionSort():
	arlen = int(sys.stdin.readline())
	temp_ar = sys.stdin.readline().split()
	ar = []
	for a in temp_ar:
		ar.append(int(a))
	i = 1
	shift = 0
	switch = False
	while i < len(ar):
		j = i
		switch = False
		while ar[j] < ar[j - 1] and j > 0:
			(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
			shift += 1
			switch = True
			j -= 1
		i += 1
	print(shift)
insertionSort()


n = 0
MAXN = 1005
l = [int for i in range(0, MAXN)]

def INIT():
	global n
	global l
	n = int(input())
	l = input().split(' ')
	for i in range(0, n):
		l[i] = int(l[i])

def SOLVE():
	global n
	global MAXN
	global l
	ans = 0
	i = 0
	j = 0
	for i in range(1, n):
		j = 0
		while (l[j] <= l[i]) & (j < i):
			j += 1
		if j < i:
			ans += i - j
			t = l[i]
			k = i
			while k > j:
				l[k] = l[k - 1]
				k -= 1
			l[j] = t
	print(ans)
INIT()
SOLVE()


L = int(input(''))
arr = input('').split()
shifts = 0
for j in range(2, L + 1):
	ar = arr[0:j]
	V = ar[-1]
	l = len(ar)
	for i in range(1, l):
		if int(V) < int(ar[l - i - 1]):
			ar[l - i] = ar[l - i - 1]
			shifts += 1
		else:
			ar[l - i] = V
			break
	else:
		ar[0] = V
	arr[0:j] = ar
print(shifts)


def main():
	N = int(input())
	arr = list(map(int, str(input()).split()))
	result = 0
	for i in range(1, N):
		if arr[i - 1] > arr[i]:
			tmp = arr[i - 1]
			arr[i - 1] = arr[i]
			arr[i] = tmp
			result += 1
			for j in range(i - 1, 0, -1):
				if arr[j - 1] > arr[j]:
					tmp = arr[j - 1]
					arr[j - 1] = arr[j]
					arr[j] = tmp
					result += 1
	print(result)
main()


def insertion_sort(ar):
	ctr = 0
	L = len(ar)
	for i in range(L):
		j = i
		if j > 0:
			while ar[j - 1] > ar[j] and j > 0:
				(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
				ctr += 1
				j -= 1
	print(ctr)
N = int(input())
A = input()
A = A.split()
A = [int(a) for a in A]
insertion_sort(A)


def main():
	size = input()
	s = input()
	array = list(map(int, s.split()))
	shifts = 0
	for i in range(1, len(array)):
		value = array[i]
		hole_pos = i
		while hole_pos > 0 and value < array[hole_pos - 1]:
			array[hole_pos] = array[hole_pos - 1]
			shifts += 1
			hole_pos -= 1
		array[hole_pos] = value
	print(shifts)
main()


def printArr(arr):
	for elt in arr:
		print(elt, end=' ')
	print()
n = int(input())
inserts = 0
args = [int(i) for i in input().split()]
for i in range(1, n):
	if args[i] < args[i - 1]:
		toInsert = args[i]
		for j in range(i, 0, -1):
			if args[j - 1] > toInsert:
				args[j] = args[j - 1]
				inserts += 1
			else:
				args[j] = toInsert
				break
			if j == 1 and toInsert < args[j]:
				args[0] = toInsert
print(inserts)


import bisect
t = int(input())
v = [int(i) for i in input().strip().split()]
v2 = []
s = 0
for (i, e) in enumerate(v):
	ind = bisect.bisect(v2, e)
	v2.insert(ind, e)
	s += i - ind
print(s)


n = int(input())
a = [int(x) for x in input().split()]
result = 0
if n == 1:
	print(0)
else:
	for i in range(1, n):
		current = a[i]
		current_old_index = i
		i -= 1
		while a[i] > current and i >= 0:
			a[i + 1] = a[i]
			i -= 1
		a[i + 1] = current
		current_new_index = i + 1
		result += current_old_index - current_new_index
	print(result)


input()
nums = list(map(int, input().split()))
orignums = nums[:]
ins = 0
for count in range(len(nums) - 1):
	for i in range(count, -1, -1):
		if nums[i] > nums[i + 1]:
			ins += 1
			(nums[i], nums[i + 1]) = (nums[i + 1], nums[i])
print(ins)


n = int(input())
a = input().split()
a = [int(i) for i in a]
count = 0
for i in range(1, n):
	val = a[i]
	j = i - 1
	while j >= 0 and val < a[j]:
		a[j + 1] = a[j]
		count += 1
		j -= 1
	a[j + 1] = val
print(count)


cases = int(input())
array = list()
i = 0
temp = ''
temp = input()
array = temp.split()
while i < cases:
	array[i] = int(array[i])
	i = i + 1
lenArray = len(array)
counter = 0
i = 1
while i < lenArray:
	j = i
	while j > 0 and array[j - 1] > array[j]:
		array[j - 1] = array[j - 1] + array[j]
		array[j] = array[j - 1] - array[j]
		array[j - 1] = array[j - 1] - array[j]
		counter = counter + 1
		j = j - 1
	i = i + 1
print(counter)


t = int(input())
l = input().split(' ')
c = 0
for i in range(t):
	l[i] = int(l[i])
for i in range(1, t):
	for j in range(i, 0, -1):
		if l[j] < l[j - 1]:
			(l[j], l[j - 1]) = (l[j - 1], l[j])
			c += 1
print(c)


def count_insertion_sort(L):
	swaps = 0
	for i in range(len(L)):
		val = L[i]
		j = i
		while j > 0 and L[j - 1] > val:
			L[j] = L[j - 1]
			j -= 1
			swaps += 1
		L[j] = val
	return swaps
n = int(input())
L = [int(s) for s in input().split()]
print(count_insertion_sort(L))


def insertion_sort(array):
	shifts = 0
	for index in range(1, len(array)):
		val = array[index]
		i = index - 1
		while i >= 0:
			if val < array[i]:
				array[i + 1] = array[i]
				array[i] = val
				i -= 1
				shifts += 1
			else:
				break
	print(shifts)
n = int(input())
vals = [int(i) for i in input().split()]
insertion_sort(vals)


s = input().split()
ar = list(map(int, input().split()))
V = ar[len(ar) - 1]
sort = len(ar) - 1
shifts = 0
for index in range(1, len(ar)):
	value = ar[index]
	i = index - 1
	while i >= 0:
		if value < ar[i]:
			ar[i + 1] = ar[i]
			ar[i] = value
			shifts += 1
			i = i - 1
		else:
			break
print(shifts)


import sys

def print_list(data):
	for element in data:
		print(element, end=' ')
	print()
length = int(sys.stdin.readline())
data = []
raw = sys.stdin.readline().split()
for index in range(length):
	data.append(int(raw[index]))
counter = 0
for index in range(1, length):
	element = data[index]
	try:
		for pointer in range(index, 0, -1):
			if data[pointer - 1] <= element:
				raise StopIteration('Place found!')
			data[pointer] = data[pointer - 1]
			counter += 1
		data[0] = element
	except StopIteration:
		data[pointer] = element
print(counter)


s = int(input())
ar = list(map(int, input().split()))
count = 0
for i in range(1, s):
	v = ar[i]
	if v >= ar[i - 1]:
		continue
	for j in range(i, 0, -1):
		if v >= ar[j - 1]:
			ar[j] = v
			break
		count += 1
		ar[j] = ar[j - 1]
	else:
		ar[0] = v
print(count)


def insertionSort(ar):
	count = 0
	for i in range(1, len(ar)):
		V = ar[i]
		j = i
		while j > 0 and ar[j - 1] > V:
			ar[j] = ar[j - 1]
			j -= 1
			count += 1
		ar[j] = V
	print(count)
s = int(input())
ar = [int(v) for v in input().split()]
insertionSort(ar)


n = int(input())
array = [int(val) for val in input().split()]
shifts = 0
for i in range(1, n):
	item = array[i]
	j = i
	while j > 0 and array[j - 1] > item:
		array[j] = array[j - 1]
		j -= 1
		shifts += 1
	array[j] = item
print(shifts)


size = int(input())
ar = list(map(int, input().split()))
count = 0
for i in range(1, len(ar)):
	for j in range(i, 0, -1):
		if ar[j] < ar[j - 1]:
			(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
			count += 1
print(count)


import copy
import math

def p(ar):
	s = ''
	for i in ar:
		s += str(i) + ' '
	print(s)

def insert(ar, tmp):
	index = 0
	for i in range(0, len(ar)):
		if i == 0 and tmp <= ar[i]:
			ar.insert(0, tmp)
			break
		elif tmp >= ar[i - 1] and tmp <= ar[i]:
			ar.insert(i, tmp)
			index = i
			break
	return index

def insertionSort(ar):
	mods = 0
	orig = copy.deepcopy(ar)
	for i in range(1, len(ar)):
		if ar[i] < ar[i - 1]:
			tmp = ar.pop(i)
			new = insert(ar, tmp)
			old = orig.index(tmp)
			mods += math.fabs(old - new)
	print(int(mods))
m = input()
ar = [int(i) for i in input().strip().split()]
insertionSort(ar)


import sys

def insertToArrayWithElement(numArray, myElementIndex):
	result = 0
	lastNum = numArray[myElementIndex]
	lastNumIndex = myElementIndex
	while lastNumIndex > 0 and lastNum < numArray[lastNumIndex - 1]:
		numArray[lastNumIndex] = numArray[lastNumIndex - 1]
		lastNumIndex = lastNumIndex - 1
		result = result + 1
	numArray[lastNumIndex] = lastNum
	return result
lines = []
for line in sys.stdin:
	lines.append(line)
arrayLen = int(lines[0])
numArray = list(map(int, lines[1].split()))
result = 0
for i in range(1, arrayLen):
	result = result + insertToArrayWithElement(numArray, i)
print(result)


n = int(input())
ar = [int(x) for x in input().split()]

def insertionsort(ar):
	swap = 0
	for i in range(1, len(ar)):
		j = i
		while j > 0 and ar[j - 1] > ar[j]:
			(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
			j = j - 1
			swap += 1
	print(swap)
insertionsort(ar)


s = int(input())
ar = list(map(int, str(input()).split()))
shifts = 0
for i in range(1, s):
	v = ar[i]
	for j in range(i, 0, -1):
		if v < ar[j - 1]:
			ar[j] = ar[j - 1]
			shifts += 1
		else:
			break
	else:
		j = 0
	ar[j] = v
print(shifts)


import sys

def insert_sort(inputA):
	global shiftsI
	shiftsI = 0
	if len(inputA) == 1:
		return inputA
	for i in range(1, len(inputA)):
		x = inputA[i]
		j = i
		while j > 0 and inputA[j - 1] > x:
			inputA[j] = inputA[j - 1]
			shiftsI += 1
			j = j - 1
		inputA[j] = x
num = int(sys.stdin.readline())
input = list((int(x) for x in sys.stdin.readline().split()))
insert_sort(input)
print(shiftsI)


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

def Insertion(A, n):
	s = 0
	for i in range(1, n):
		j = i
		while A[j] < A[j - 1] and j > 0:
			(A[j], A[j - 1]) = (A[j - 1], A[j])
			j -= 1
			s += 1
	return s
print(Insertion(A, n))


import sys

def insertion_sort(arr, s):
	countr = 0
	for v in range(1, len(array)):
		value = arr[v]
		x = v - 1
		while x >= 0 and arr[x] > value:
			arr[x + 1] = arr[x]
			x -= 1
			countr += 1
		arr[x + 1] = value
	print(countr)
size = int(sys.stdin.readline().strip())
array = sys.stdin.readline().strip().split()
array = [int(x) for x in array]
insertion_sort(array, size)


input()
ar = [int(i) for i in input().split()]

def isort(ar):
	swaps = 0
	if len(ar) > 1:
		for i in range(1, len(ar)):
			j = i
			while ar[j - 1] > ar[j] and j > 0:
				(ar[j], ar[j - 1]) = (ar[j - 1], ar[j])
				swaps += 1
				j -= 1
	print(swaps)
isort(ar)


s = int(input())
ar = [int(e) for e in input().split()]
moves = 0
for j in range(1, s):
	tgt = ar[j]
	i = j - 1
	while i >= 0 and ar[i] > tgt:
		moves += 1
		ar[i + 1] = ar[i]
		i -= 1
	ar[i + 1] = tgt
print(moves)


s = int(input())
ar = [int(i) for i in str(input()).split()]
ans = 0
for i in range(1, s):
	x = ar[i]
	j = i
	while j > 0 and ar[j - 1] > x:
		ans += 1
		ar[j] = ar[j - 1]
		j -= 1
	ar[j] = x
print(ans)


T = int(input())
array = []
for item in input().split():
	array.append(int(item))
count = 0
for x in range(1, len(array)):
	j = x
	while array[j - 1] > array[j] and j > 0:
		array[j] = array[j] + array[j - 1]
		array[j - 1] = array[j] - array[j - 1]
		array[j] = array[j] - array[j - 1]
		count += 1
		j -= 1
print(count)


def insertionSort(ar):
	shifts = 0
	for pos in range(len(ar) - 1):
		val = ar[pos + 1]
		while pos >= 0 and ar[pos] > val:
			ar[pos + 1] = ar[pos]
			pos -= 1
			shifts += 1
		ar[pos + 1] = val
	print(shifts)
input()
ar = [int(x) for x in input().split()]
insertionSort(ar)


n = int(input())
L = input().split()
shifts = 0
for i in range(1, n):
	for j in range(i - 1, -1, -1):
		if int(L[i]) < int(L[j]):
			tmp = L[i]
			L[i] = L[j]
			L[j] = tmp
			shifts += 1
			i = i - 1
		else:
			break
print(shifts)


N = int(input())
arr = [int(i) for i in input().split()]
count = 0
for j in range(0, N - 1):
	for i in range(0, N - 1):
		if arr[i] > arr[i + 1]:
			count = count + 1
			tmp = arr[i]
			arr[i] = arr[i + 1]
			arr[i + 1] = tmp
print(count)


N = int(input())
arr = [int(x) for x in input().split()]
num_shifts = 0
for i in range(1, len(arr)):
	for j in range(1, i + 1):
		if arr[i - j] > arr[i - j + 1]:
			num_shifts += 1
			temp = arr[i - j]
			arr[i - j] = arr[i - j + 1]
			arr[i - j + 1] = temp
		else:
			break
print(num_shifts)


N = int(input())
inp = list(map(int, input().split()))
counter = 0
for i in range(1, N):
	j = i
	while j > 0 and inp[j - 1] > inp[j]:
		(inp[j], inp[j - 1]) = (inp[j - 1], inp[j])
		j = j - 1
		counter = counter + 1
print(counter)


size = int(input())
ar = [int(x) for x in input().split()]

def insert_sort(ar):
	shift_count = 0
	for sort_point in range(1, len(ar)):
		i = sort_point
		while ar[i - 1] > ar[i] and i > 0:
			(ar[i], ar[i - 1]) = (ar[i - 1], ar[i])
			shift_count += 1
			i -= 1
	return shift_count
print(insert_sort(ar))


def backSwap(arr, j):
	A = arr[j]
	B = arr[j - 1]
	arr[j] = B
	arr[j - 1] = A

def insertion_sort(l):
	counter = 0
	for i in range(1, len(l)):
		j = i
		while j > 0 and l[j] < l[j - 1]:
			backSwap(l, j)
			counter += 1
			j = j - 1
	return counter
m = int(input().strip())
ar = [int(i) for i in input().strip().split()]
swaps = insertion_sort(ar)
print(swaps)


def insertion_sort(l):
	count = 0
	for i in range(1, len(l)):
		j = i - 1
		key = l[i]
		while l[j] > key and j >= 0:
			l[j + 1] = l[j]
			j -= 1
			count += 1
		l[j + 1] = key
	print(count)
m = int(input().strip())
ar = [int(i) for i in input().strip().split()]
insertion_sort(ar)


def insertion_sort(l):
	t = 0
	for i in range(1, len(l)):
		a = 0
		j = i - 1
		key = l[i]
		while l[j] > key and j >= 0:
			l[j + 1] = l[j]
			j -= 1
			t += 1
		l[j + 1] = key
	return t
m = int(input().strip())
ar = [int(i) for i in input().strip().split()]
print(insertion_sort(ar))


def insertion(a):
	count = 0
	for i in range(1, len(a)):
		j = i - 1
		while j >= 0 and a[j] > a[j + 1]:
			(a[j + 1], a[j]) = (a[j], a[j + 1])
			count += 1
			j -= 1
	return count
n = int(input())
a = [int(x) for x in str(input()).split()]
print(insertion(a))


def insertion_sort(l):
	shifts = 0
	for i in range(1, len(l)):
		j = i - 1
		key = l[i]
		while l[j] > key and j >= 0:
			l[j + 1] = l[j]
			j -= 1
			shifts += 1
		l[j + 1] = key
	print(shifts)
m = int(input().strip())
ar = [int(i) for i in input().strip().split()]
insertion_sort(ar)


def insertion_sort(l):
	z = 0
	for i in range(1, len(l)):
		j = i - 1
		key = l[i]
		while l[j] > key and j >= 0:
			l[j + 1] = l[j]
			j -= 1
			z += 1
		l[j + 1] = key
	return z
input()
z = list(map(int, input().split()))
print(insertion_sort(z))


l = int(input())
a = list(input())
b = []
for x in range(0, l):
	b.append('')
index = 0
for x in range(0, len(a)):
	if a[x] != ' ':
		b[index] += a[x]
	if a[x] == ' ':
		index += 1
for x in range(0, len(b)):
	b[x] = int(b[x])

def foo(ls):
	r = ls
	temp = r[len(r) - 1]
	for x in range(len(r) - 2, -1, -1):
		if r[x] > temp:
			r[x + 1] = r[x]
		if r[x] <= temp:
			r[x + 1] = temp
			return r
		if x == 0:
			r[0] = temp
			return r
			break
c = list(b)
dif = 0
ans = 0
for a in range(2, l + 1):
	b[0:a] = foo(b[0:a])
	if b[a - 1] != c[a - 1]:
		for x in range(0, a - 1):
			if b[x] == c[a - 1]:
				dif = a - 1 - x
		ans += dif
	c = list(b)
print(ans)


import sys
length = input()
try:
	templist = input()
except:
	print(sys.exc_value)
array = list(map(lambda x: int(x), templist.split()))
n = 0
for i in range(int(length)):
	for j in range(i):
		if array[i] < array[j]:
			ele = array[i]
			array.pop(i)
			array.insert(j, ele)
			n = n + i - j
print(n)


n = int(input())
array = [int(i) for i in input().split()]
shifts = 0
l = len(array)
ar = [array.pop(0)]
for i in range(l - 1):
	k = shifts
	v = array.pop(0)
	ar.append(v)
	inserted = False
	n = len(ar)
	for i in range(n - 2, -1, -1):
		if ar[i] > v:
			ar[i + 1] = ar[i]
			shifts += 1
		else:
			ar[i + 1] = v
			inserted = True
			break
	if not inserted:
		ar[0] = v
print(shifts)


__author__ = 'pvkcse'
__studentat__ = 'Accet,kkdi'
import sys

class insertion_sort:

	def __init__(self, lists, length):
		self.lists = lists
		self.length = length

	def ins_sort(self):
		count = 0
		for i in range(1, self.length):
			value = self.lists[i]
			place = i
			while place > 0 and self.lists[place - 1] > value:
				self.lists[place] = self.lists[place - 1]
				place -= 1
				count += 1
			self.lists[place] = value
		return count

def main():
	int(input())
	lists = list(map(int, sys.stdin.readline().split()))
	unsortedlist = insertion_sort(lists, len(lists))
	print(unsortedlist.ins_sort())
main()


def insertion_sort(a):
	count = 0
	for i in range(len(a)):
		for j in reversed(range(i)):
			i = j + 1
			if a[j] > a[i]:
				count += 1
				(a[i], a[j]) = (a[j], a[i])
			else:
				break
	return count

def solve():
	N = int(input())
	a = list(map(int, input().split()))
	answer = insertion_sort(a)
	print(answer)
solve()


def insertionsort(a):
	count = 0
	length = len(a)
	for x in range(1, length):
		key = a[x]
		prev = x - 1
		while prev >= 0 and a[prev] > key:
			a[prev + 1] = a[prev]
			prev -= 1
			count += 1
		a[prev + 1] = key
	return count

def makelistsameline(strnos, N):
	strnos = strnos.split()
	widtharray = []
	for i in range(N):
		widtharray.append(int(strnos[i]))
	return widtharray
N = int(input())
L = makelistsameline(input(), N)
print(insertionsort(L))


def insertion_sort(l):
	c = 0
	for i in range(1, len(l)):
		j = i - 1
		key = l[i]
		while l[j] > key and j >= 0:
			l[j + 1] = l[j]
			j -= 1
			c += 1
		l[j + 1] = key
	return c
m = int(input().strip())
ar = [int(i) for i in input().strip().split()]
print(insertion_sort(ar))


def insertion_sort(l):
	s = 0
	for i in range(1, len(l)):
		j = i - 1
		key = l[i]
		while l[j] > key and j >= 0:
			l[j + 1] = l[j]
			s += 1
			j -= 1
		l[j + 1] = key
	return s
m = int(input().strip())
ar = [int(i) for i in input().strip().split()]
print(insertion_sort(ar))


def insert_sort(n, arr):
	shifts = 0
	for i in range(n):
		x = arr[i]
		j = i
		while j > 0 and arr[j - 1] > x:
			arr[j] = arr[j - 1]
			j -= 1
		arr[j] = x
		shifts += i - j
	print(shifts)

def main():
	n = int(input())
	arr = [int(x) for x in input().split()]
	insert_sort(n, arr)
main()


def insertion_sort(l):
	it = 0
	for i in range(1, len(l)):
		j = i - 1
		key = l[i]
		while l[j] > key and j >= 0:
			l[j + 1] = l[j]
			it += 1
			j -= 1
		l[j + 1] = key
	return it
m = int(input().strip())
ar = [int(i) for i in input().strip().split()]
it = insertion_sort(ar)
print(it)


def insertionSort(l):
	shifts = 0
	for i in range(1, len(l)):
		val = l[i]
		for j in range(i, 0, -1):
			if l[j - 1] > val:
				l[j] = l[j - 1]
				shifts += 1
				if j == 1:
					l[0] = val
			else:
				l[j] = val
				break
	print(shifts)
n = int(input())
l = [int(x) for x in input().split()]
assert n == len(l)
insertionSort(l)


class xSorts:

	def Shift_left(Ra_, Idx_):
		tmp = Ra_[Idx_ - 1]
		Ra_.remove(tmp)
		Ra_.insert(Idx_, tmp)

class InsertionSort(xSorts):

	def __init__(self, Ra_):
		self._ra = Ra_
		self._len = len(self._ra)

	def Sort(self):
		shift_count = 0
		if self._len < 2:
			return 0
		for idx in range(1, self._len):
			for shift_idx in range(idx, 0, -1):
				if ra[shift_idx] < ra[shift_idx - 1]:
					InsertionSort.Shift_left(self._ra, shift_idx)
					shift_count += 1
		return shift_count
num_tests = int(input().strip())
ra = list(map(int, input().strip().split()))
i_sort = InsertionSort(ra)
shift_count = i_sort.Sort()
print(shift_count)


def insertion_sort(l):
	count = 0
	for i in range(1, len(l)):
		j = i
		key = l[i]
		while j > 0 and l[j - 1] > key:
			l[j] = l[j - 1]
			j -= 1
			count = count + 1
		l[j] = key
	print(count)
m = int(input().strip())
ar = [int(i) for i in input().strip().split()]
insertion_sort(ar)


def converter(x):
	return int(x)
nombreChiffre = int(input())
sequence = input()
desordonnee = sequence.split()
desordonnee = list(map(converter, desordonnee))
compteDecalage = 0
for i in range(1, len(desordonnee)):
	pivot = desordonnee[i]
	j = i - 1
	while j >= 0 and pivot < desordonnee[j]:
		desordonnee[j + 1] = desordonnee[j]
		desordonnee[j] = pivot
		compteDecalage += 1
		j -= 1
ordonnee = desordonnee
print(compteDecalage)


def insertion_sort(l):
	total = 0
	for i in range(1, len(l)):
		j = i
		key = l[i]
		while (j > 0 and l[j - 1]) > key:
			total += 1
			l[j] = l[j - 1]
			j -= 1
		l[j] = key
	return total
m = int(input().strip())
ar = [int(i) for i in input().strip().split()]
t = insertion_sort(ar)
print(str(t))