Skip to content

Instantly share code, notes, and snippets.

@andreis
Created Feb 24, 2014
Embed
What would you like to do?
#!/usr/bin/env python3
# https://www.hackerrank.com/challenges/insertion-sort
'''
0 1 2 3 .. n-1
n = 6
3 1 2 5 1 2 array
4 0 1 2 0 0 DP array
0 1 1 0 3 2 substitutions
3 0
1 3 1
1 2 3 1
1 2 3 5 0
1 1 2 3 5 3
1 1 2 2 3 5 2
'''
tests = int(input())
out = ''
for _idx in range(tests):
n = int(input())
a = [int(s) for s in input().split()]
total = 0
for i in range(n-2, -1, -1):
for j in range(i+1, n):
if a[i] > a[j]:
total += 1
out += str(total) + '\n'
print(out[:-1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment