Programming Project: write a function$$count$\_$inversions$($input$\_$list$)$:$$that takes in a list as input, and returns the number of inversions. An inversion in input$\_$List is a pair of elements x and y $($of the list$)$ such that x appears before y in input$\_$List, but x $>$ y$.$

Use base code given and do not delete any of the code:

def merge$\_$and$\_$count$($arr$,$ left, mid, right$)$:

# $1.$ Initialize inversion count to $0.$

inv$\_$count $=0$

# $2.$ Create temporary arrays to hold the values of the left and right halves of the original array.

# $3.$ Initialize counters and indices for merging.

# $4.$ Merge the two halves:

# a$.$ Compare elements from the left and right halves.

# b$.$ If an element in the left half is greater than an element in the right half, increment the inversion count.

# c$.$ Copy the smaller element to the original array.

# $5.$ Copy any remaining elements from the left and right temporary arrays back to the original array.

# $6.$ Return the inversion count.

# YOUR CODE HERE Steps above are to help you implement the function

return inv$\_$count

def merge$\_$sort$\_$and$\_$count$($arr$,$ left, right$)$:

# $1.$ Initialize inversion count to $0.$

inv$\_$count $=0$

# $2.$ If the left index is less than the right index:

# a$.$ Calculate the middle index.

# b$.$ Recursively call merge$\_$sort$\_$and$\_$count for the left half of the array.

# c$.$ Recursively call merge$\_$sort$\_$and$\_$count for the right half of the array.

# d$.$ Call merge$\_$and$\_$count to merge the two halves and count the inversions between them.

# e$.$ Accumulate the inversion counts from the above steps.

# $3.$ Return the total inversion count.

# YOUR CODE HERE Steps above are to help you implement the function

return inv$\_$count

# Do not change the function name

def count$\_$inversions$($input$\_$list$)$:

# $1.$ Create a copy of the input list to avoid modifying the original list.

arr $=$ input$\_$list.copy$()$

# $2.$ Call merge$\_$sort$\_$and$\_$count with the copied array, starting indices $0$ and ending index $($length of array $-1).$

# $3.$ Return the total inversion count.

# YOUR CODE HERE Steps above are to help you implement the function

return merge$\_$sort$\_$and$\_$count$($arr$,0,$ len$($arr$)-1)$

# Example usage:

if $\_\_$name$\_\_=="\_\_$main$\_\_"$:

input$\_$list $=[5,4,3,2,1]$

print$($count$\_$inversions$($input$\_$list$))$ # Output: $10$

input$\_$list $=[1,5,2,8,3,4]$

print$($count$\_$inversions$($input$\_$list$))$ # Output: $5$

input$\_$list $=[1,2,3,4,5]$

print$($count$\_$inversions$($input$\_$list$))$ # Output: $0$

input$\_$list $=[1,2,3,5,4]$

print$($count$\_$inversions$($input$\_$list$))$ # Output: $1$