c++ O(n) time & space 13 ms
\n// i/o hack\nauto __NEEDFORSPEED__ = [](){ std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();\n\nclass Solution {\npublic:\n    int bestRotation(
```\n// i/o hack\nauto __NEEDFORSPEED__ = [](){ std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();\n\nclass Solution {\npublic:\n    int bestRotation(vector<int>& a) {\n        int n = a.size();\n        vector<int> pp(n+5);\n        \n        int sum = 0;\n        for(int i=0; i<n; i++){\n            int v = a[i];\n            if(v <= i) sum++;\n            if(v != 0 && v != n){\n                pp[((i-v+n)%n)+1]--;\n                pp[i+1]++;\n            }\n        }\n        \n        \n        int hi = 0, hisum = sum;\n        \n        for(int i=1; i<n; i++){\n            sum += pp[i];\n            if(sum > hisum) hi = i, hisum = sum;\n        }\n        \n        return hi;\n        \n    }\n};\n```
[]