O(N) solution rotating indices instead of A
The idea is rotating indices instead of A. Say A[0]\'s index is x, we have:\nA|A[0]|A[1]|A[2]|...|A[n-1-x]|A[n-x]|A[n-x+1]|...\n--|--|--|--|--|--|--|--|--\ninde
The idea is rotating indices instead of `A`. Say `A[0]`\'s index is `x`, we have:\nA|A[0]|A[1]|A[2]|...|A[n-1-x]|A[n-x]|A[n-x+1]|...\n--|--|--|--|--|--|--|--|--\nindex|x|x+1|x+2|...|x+(n-1-x) = n-1|0|1|...\nThen for each `A[i]`, consider `A[i]` can get 1 point from what `x`-es:\n* **A[i] \u2264 x + i && i \u2264 n - 1 - x**, or\n* **A[i] \u2264 i - (n - x) && i \u2265 n - x**\n\nSimplified:\n*  **A[i] - i \u2264 x \u2264 n - 1 - i**\n*  **x \u2265 n - i + A[i]**\n\nThen we can calculate total score for each `x` using SegmentTree or BinaryIndexTree in O(NlogN), or "accumulating preifx difference" in O(N).\n\n```\nconstexpr int N = 20000;\nint B[N + 1], n;\n\ninline void add(int l, int r) {\n    l = max(0, l);\n    r = min(n - 1, r);\n    if (l <= r) ++B[l], --B[r + 1];\n}\n\nclass Solution {\npublic:\n    int bestRotation(vector<int>& A) {\n        n = A.size();\n        memset(B, 0, sizeof(B[0]) * (n + 1));\n        for (int i = 0; i < n; ++i) {\n            add(A[i] - i, n - 1 - i);\n            add(n - i + A[i], n - 1);\n        }\n        int mx = B[0], res = 0;\n        for (int x = 1; x < n; ++x) {\n            B[x] += B[x - 1];\n            int k = n - x;\n            if (B[x] > mx || B[x] == mx && k < res) mx = B[x], res = k;\n        }\n        return res;\n    }\n};\n```
[]