[Python] Observational Question O(N)
\n# Code\ncpp []\nclass Solution {\npublic:\n    int bestRotation(vector<int>& nums) {\n        int n = nums.size();\n        pair<int,int> ans = {0,0};\n      
\n# Code\n```cpp []\nclass Solution {\npublic:\n    int bestRotation(vector<int>& nums) {\n        int n = nums.size();\n        pair<int,int> ans = {0,0};\n        vector<int> dk(n+1);\n        for(int i=0;i<n;i++) {\n            dk[0] += 1;\n            nums[i] = i-nums[i];\n            dk[max(-1,min(i,nums[i]))+1]--;\n            if(nums[i]>=0) {\n                ans.first++;\n            }\n        }\n        for(int i=1;i<=n;i++) {\n            dk[i] +=dk[i-1];\n        }\n        int cur = -n;\n        int cnt = 0;\n        unordered_map<int,int> cc;\n        for(int k=1;k<n;k++) {\n            cnt -= cc[cur++];\n            if(nums[k-1]>=k-n) {\n                cc[nums[k-1]]++;\n                cnt++;\n            }\n            ans = max(ans,{cnt+dk[k],-k});\n        }\n        return -ans.second;\n    }\n};\n```
['C++']