Diff Array
It is easy to find the solution that we calculate the available range of K for every i.\nAfter rotation by K, an index of i will be (i - K + N) % N.\nWe want af
It is easy to find the solution that we calculate the available range of K for every i.\nAfter rotation by K, an index of i will be (i - K + N) % N.\nWe want after index, A[i] <= i:\nso A[i] - (i - k + N) % N <= 0;\nso  if (i < k) , we need A[i] - (N + i - k)  <= 0 -> A[i] - N - i + k <= 0 -> k <= i + N - A[i]\nand if (i >= k) we need A[i] - (i - k) <= 0 -> A[i] - i + k <= 0 -> k <= i - A[i]\nFor each i, we add range (i, min(i + N - A[i], N-1)] and [0, max(i - A[i], 0)] by step 1;\nAnd find the maximum k.\nWe use Diff Arry to add range with in O(1).\nDiff array is an array a where a[i] means raw[i]-raw[i-1], so we just `a[x]++ a[y+1]--` to add range(x,y) by 1;\n\n```c++\nclass Solution {\npublic:\n    int bestRotation(vector<int>& A) {\n        // index i -> (i - K + N) % N\n        int N = A.size();\n        vector<int> diff(N, 0);\n        for (int i = 0; i < N; i++) {\n            // rotate i : i -> 0 min\n            // rotate i + 1: i > N-1 max\n            /*\n            A[i] - (i - k + N) % N <= 0;\n            if (i < k) {\n                A[i] - (N + i - k)  <= 0;\n                A[i] - N - i + k <= 0;\n                k <= i + N - A[i];\n            } else {\n                A[i] - (i - k) <= 0;\n                A[i] - i + k <= 0;\n                k <= i - A[i];\n            }\n            so\n            i < k <= min(i + N - A[i], N-1) or k <= i - A[i]\n            (i, min(i + N - A[i], N-1)]\n            [0, max(i - A[i], 0)]\n            */\n            // add [i+1, i + N - A[i]]\n            if (i + 1 < N && i + 1 <= i + N - A[i]) { \n                diff[i+1]++; \n                if (i + N - A[i] + 1 < N) diff[i + N - A[i] + 1]--;\n            }\n            if (i - A[i] >= 0 && i - A[i] < N) {\n                diff[0]++;\n                if (i - A[i] + 1 < N) diff[i - A[i] + 1]--; \n            } \n        }\n        for (int i = 1; i < N; i++) diff[i] += diff[i-1];\n        int maxi = *max_element(diff.begin(), diff.end());\n        for (int i = 0; i < N; i++) if (diff[i] == maxi) return i;\n        return N;\n    }\n};\n```
[]