Python (n * log n) with explanations
Say we have array a[0], a[1], ..., a[n-1] convert it to a[0] - 0, a[1] - 1, ..., a[n-1] - (n-1). Number of elements not greater than zero in new array is number
Say we have array `a[0], a[1], ..., a[n-1]` convert it to `a[0] - 0, a[1] - 1, ..., a[n-1] - (n-1)`. Number of elements not greater than zero in new array is number of points in zero rotation. Now say we do rotation to the left, then if we compute number of elements not greater than one in `a[0] - 0, a[1] - 1, ..., a[n-2] - (n-2)`, and in `a[n-1] - (n-1) + n` we get number of points for left rotation by one. Similarly just keep track of your left subbarray and right subarray in `SortedList` class, so that using bisect we can answer to the query of less than or equal some value in `log n` time.  \n\n```\nfrom sortedcontainers import SortedList\n\nclass Solution:\n    def bestRotation(self, nums):\n        n = len(nums)\n        nums = [k - i for i, k in enumerate(nums)]\n        left = SortedList(nums)\n        right = SortedList()\n\n        maxx = (left.bisect_right(0), 0)\n        for k in range(1, n):\n            i = n - k\n            left.remove(nums[i])\n            right.add(nums[i] + n)\n\n            point = left.bisect_right(k) + right.bisect_right(k)\n            maxx = max(maxx, (point, -i))\n        return -maxx[1]\n```
[]