# Calculating the total sum of inversion count for all subarrays

My approach was to visit all inversion count pair and count how many subarrays these pair contribute. Visiting every pair requires $$\\mathcal{O}(n^2)\$$ time, but I want an optimized version of this, something like $$\\mathcal{O}(n \log n)\$$.

Can I do something with the Fenwick tree? Inversion in an array Fenwick tree

e.g. if arr = [1,3,4,2] , then total inversion count for all subarrays = 5.

number = int(input("Input number := "))
main_list = list(map(int,input().split()))

• Since you are only concerned with i < j why not put j in range(i + 1, n)? – Austin Hastings Oct 9 at 15:41
• Your original code works. The edit by @brijeshkalkani changed n to number in several places, but k = (i+1) * (n-j) remained unchanged. It also changed l to main_list, but didn't change all occurrences, and mistyped one occurrence as mail_list. Moreover, it changed spacing (a PEP review comment) and added a prompt to an input() that never existed. The edit should never have been approved. – AJNeufeld Oct 9 at 21:40