N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.
버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.
첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다.
첫째 줄에 Swap 횟수를 출력한다
def split(lst, n):
if n == 1:
return lst
left = lst[:n // 2]
right = lst[n // 2:]
left = split(left, len(left))
right = split(right, len(right))
return merge(left, right)
def merge(left, right):
global cnt
check = []
i = j = 0
while i < len(left) or j < len(right):
if i < len(left) and j < len(right):
if left[i] <= right[j]:
check.append(left[i])
i += 1
else:
check.append(right[j])
j += 1
cnt += len(left) - i
elif len(left) > i:
check.append(left[i])
i += 1
elif len(right) > j:
check.append(right[j])
j += 1
return check
n = int(input())
lst = list(map(int, input().split()))
cnt = 0
split(lst, n)
print(cnt)