# give a list, compare it with the ascedning sorted result, total how many numbers
# in wrong positions
import collections
from random import randint


class Solution(object):

    def wrongPositions(self, arr):
        res = 0
        # print arr
        sorted = self.countingSort(arr)
        # print sorted

        for i in xrange(0, len(arr)):
            if arr[i] != sorted[i]:
                res += 1
        return res

    def countingSort(self, arr):
        m, d, n = max(arr), collections.Counter(arr), len(arr)
        count = [0] * (m + 1)

        count[0] = d[0]
        for i in xrange(1, m + 1):
            count[i] = count[i - 1] + d[i]

        sorted = [0] * n

        for i in xrange(0, n):
            sorted[count[arr[i]] - 1] = arr[i]
            count[arr[i]] -= 1

        return sorted

    def compareList(self, a, b):
        b = sorted(a)
        res = 0
        for i in xrange(len(b)):
            if a[i] != b[i]:
                res += 1

        return res


if __name__ == '__main__':
    a = [1, 0, 3, 2, 4, 5]
    print Solution().wrongPositions(a)
    print Solution().compareList(a, sorted(a))

    a = [320, 530, 13, 36, 282, 119, 722, 649, 302, 103, 612, 233, 0, 172, 552, 466, 803, 143, 316, 32]
    print Solution().wrongPositions(a)
    print Solution().compareList(a, sorted(a))

    for i in xrange(100):
        a = [randint(0, 1000) for _ in xrange(200)]
        if Solution().wrongPositions(a) != Solution().compareList(a, sorted(a)):
            print "something wrong"
    print "all correct"
