C++ interval accumulation
Consider the element A[i]:\n\n- If A[i] <= i, then to get 1 point for this element, K has to be in either [0,i-A[i]] or [i+1, N].\n- If A[i] > i, then to get 1 
Consider the element `A[i]`:\n\n- If `A[i] <= i`, then to get `1` point for this element, `K` has to be in either `[0,i-A[i]]` or `[i+1, N]`.\n- If `A[i] > i`, then to get `1` point for this element, `K` has to be in `[i+1, N-A[i]+i]`\n\nThe problem is then converted to the interval accumulation problem: we scan each element in `A` and accumulate their effective intervals. For each interval `[a,b]`, one score is added to all numbers between `a` and `b`. At the end, we return the `K` with the maximum score. The classical `O(N)` solution for this interval accumulation problem is used.\n\n```\nclass Solution {\npublic:\n    int bestRotation(vector<int>& A) {\n        const int N = A.size();\n        // vector to accumulate intervals\n\t\t// For a position k, the accumulated score is the sum of tmp[0] + ... + tmp[k]\n        vector<int> tmp(N+1, 0); \n        \n        for (int i(0); i < N; ++i) {\n            if (A[i] <= i) {\n                // if A[i] <= i, K in [0,i-A[i]] or [i+1, N-1] to get 1 point\n                tmp[0] += 1;\n                tmp[i-A[i]+1] -= 1;\n                tmp[i+1] += 1;\n                tmp[N] -= 1;\n            }\n            else {\n                // if A[i] > i, K in [i+1, N-A[i]+i] to get 1 point \n                tmp[i+1] += 1;\n                tmp[N-A[i]+i+1] -= 1;\n            }\n        }\n        \n        // count to get maximum\n        int maxc = INT_MIN;\n        int maxK = -1;\n        int cur = 0;\n        for (int i(0); i < N; ++i) {\n            cur += tmp[i];\n            if (cur > maxc) {\n                maxc = cur;\n                maxK = i;\n            }\n        }\n        return maxK;\n    }\n};\n```
['C++']