Kotlin Solution O(n)
\nclass Solution {\n    fun bestRotation(A: IntArray): Int {\n        // after scoreDiffs is filled in, scoreDiffs[0] will be the score when K is 0,\n        //
```\nclass Solution {\n    fun bestRotation(A: IntArray): Int {\n        // after scoreDiffs is filled in, scoreDiffs[0] will be the score when K is 0,\n        // and for 0 < i < A.size, scoreDiffs[i] will be (score when K is i) - (score when K is i - 1).\n        val scoreDiffs = IntArray(A.size + 1)\n        for((index, a) in A.withIndex()) {\n            scoreDiffs[index + 1] += 1\n            scoreDiffs[minOf(A.size - 1, A.size - a + index) + 1] -= 1\n            if (a <= index) {\n                scoreDiffs[0] += 1\n                scoreDiffs[index - a + 1] -= 1\n            }\n        }\n        var res = 0\n        var runningTotal = 0\n        var maxRunningTotal = 0\n        for ((index, scoreDiff) in scoreDiffs.withIndex()) {\n            runningTotal += scoreDiff\n            res = if (runningTotal > maxRunningTotal) index else res\n            maxRunningTotal = maxOf(maxRunningTotal, runningTotal)\n        }\n        return res\n    }\n}\n```
[]