Segment Tree Solution C++
\nclass Solution {\npublic:\n    static const int maxN = 1e5;\n    int seg[4*maxN + 5];\n    int lazy[4*maxN + 5];\n    void update(int l,int r,int uL,int uR,in
```\nclass Solution {\npublic:\n    static const int maxN = 1e5;\n    int seg[4*maxN + 5];\n    int lazy[4*maxN + 5];\n    void update(int l,int r,int uL,int uR,int ind,int x){ // update query with lazy propagation\n        if(lazy[ind] != 0){\n            seg[ind] += lazy[ind];\n            if(l != r){\n                lazy[2*ind+1] += lazy[ind];\n                lazy[2*ind+2] += lazy[ind];\n            }\n            lazy[ind] = 0;\n            \n        }\n        if(uL>r || uR < l)return;\n        if(uL <= l && uR >= r){\n            seg[ind] += x;\n            if(l != r){\n                lazy[2*ind+1] += x;\n                lazy[2*ind+2] += x;\n            }\n            return;\n        }\n        int mid = l + (r-l)/2;\n        update(l,mid,uL,uR,2*ind+1,x);\n        update(mid+1,r,uL,uR,2*ind+2,x);\n        seg[ind]  = max(seg[2*ind+1],seg[2*ind+2]); \n    }\n    int query(int l,int r,int uL,int uR,int ind){ // range query for segment tree\n        if(lazy[ind] != 0){\n            seg[ind] += lazy[ind];\n            if(l != r){\n                lazy[2*ind+1] += lazy[ind];\n                lazy[2*ind+2] += lazy[ind];\n            }\n            lazy[ind] = 0;\n        }\n        if(uL>r || uR < l)return INT_MIN;\n        if(uL <= l && uR >= r)return seg[ind];\n        int mid = l + (r-l)/2;\n        int left = query(l,mid,uL,uR,2*ind+1);\n        int right = query(mid+1,r,uL,uR,2*ind+2);\n        return max(left,right);\n    }\n    \n    int bestRotation(vector<int>& nums) {\n        int n = nums.size();\n        memset(seg,0,sizeof(seg[0])*n);\n        memset(lazy,0,sizeof(lazy[0])*n);\n        for(int i = 0;i<nums.size();i++){\n            int leftShiftAdd =  i - nums[i];\n            if(leftShiftAdd>=0){\n\t\t\t// range of left rotations this element  can make to stay in scoring  scoring zone towards its left\n                update(0,n-1,0,leftShiftAdd,0,1);\n            }\n            if(i == n-1)continue;\n            int rightShiftLow = max(i+1,nums[i]);\n            int reachUp =  n - (rightShiftLow - i);\n            int reachDown =  n - (n-1 - i);\n\t\t\t// range of left rotations this element  can make to stay in scoring  scoring zone towards its right\n            update(0,n-1,reachDown,reachUp,0,1);\n\t\t\t\n        }\n\t\t// finding maximum of all segment tree indexes\n        int maxi = 0;\n        int ind = -1;\n        for(int i = 0;i<n;i++){\n            int a = query(0,n-1,i,i,0);\n            if(maxi< a){\n                maxi = a;\n                ind = i;\n            }\n        }\n\n        \n        return ind;\n    }\n};\n```
['Tree']