Would anybody help me understand the case where my logic is not holding true?

Make ‘k’ , ‘s1’, ‘s2’, ‘ans’ as long variable. Might help you :slight_smile:

Used long long…check the macros.
Issue isn’t with the size of output, I guess this logic fails for certain cases hence the WA.But I can’t seem to work out the fail case.

I used unsigned long, was absolutely sufficient.

The solutions is this:

x = ( v * (K+1) * K + w * K * (K-1) ) / 2

v = number of inversions in the number sequence
w = number of non-inversions in the number sequence (and two equal A_i, A_j are not non-inversions)

Runtime of my algorithm (in C) was 0.02sec :wink:

The important fact is that inversions turn into non-inversions when the sequence is repeated. Then the formula can easily be derived.