Java not fast segment tree + lazy propagation solution O(NlogN) with explaination
Before I read the solution, I came up with an idea of using segment tree to \nsolve this problem, even if it is unnecessary I think it is still a good practice 
Before I read the solution, I came up with an idea of using segment tree to \nsolve this problem, even if it is unnecessary I think it is still a good practice for \nsegment tree and lazy propagation. The idea is for each element in the\narray, it only has two intervals of rotate value such that a point could be gained\nfor this element. Then we can simply maintain a maximum segment tree and then when we\ndo the iteration we simply keeps increment the rangesum by 1. When the iteration ends\nwe can query for each i in the tree and see if it is equal to the max value\nif so, we return the first occurrence one.\n\n```\nclass Solution {\n    public int bestRotation(int[] A) {\n\t\t// two edge cases\n        if (A.length == 0) return 0;\n        if (A.length == 1) return 0;\n\t\t// instantiate\n        SegmentTree t = new SegmentTree(A.length);\n        int i;\n\t\t// for each number in the array increment the range of rotations that could bring\n\t\t// 1 point by 1\n        for (i = 0 ; i < A.length; i++) {\n            // when the number is originally in a valid position, there\'s two intervals\n\t\t\t// of rotation number that could gain 1 point\n\t\t\t// 0 to i - A[i]\n\t\t\t// or i + 1 to A.length - 1\n            if (A[i] <= i) {\n                t.update(0, i - A[i], 1);\n                t.update(i + 1, A.length - 1, 1);\n            } else {\n\t\t\t\t// otherwise, only one interval of rotation number could gain 1 point\n\t\t\t\t// i + 1 to A.length - A[i] + 1\n\t\t\t\t// these numbers could easily be derived by drawing intervals\n                t.update(i + 1, A.length - A[i] + i, 1);\n            } \n        }\n        // find the maximum point that can be gained\n        int k = t.query(0, A.length - 1);\n        // see what number of rotation could meet this maximum point and return it\n        for (i = 0 ; i < A.length; i++) {\n            if (t.query(i, i) == k) {\n                return i;\n            }\n        }\n        \n        return -1;\n    }\n}\n\nclass SegmentTree {\n    private int[] tree;\n    private int[] lazy;\n    int N;\n    public SegmentTree(int N) {\n        this.N = N;\n        this.tree = new int[65537];\n        this.lazy = new int[65537];\n    }\n    \n    public int query(int l, int r) {\n        return queryUtil(l, r, 0, this.N - 1, 1);\n    }\n    \n    public void update(int l, int r, int add) {\n        updateUtil(l, r, 0, this.N - 1, 1, 1);\n    }\n    \n    private int queryUtil(int l, int r, int start, int end, int index) {\n        // invalid\n        if (l > r || start > end) return -1;\n\t\t// lazy propagation\n        if (lazy[index] != 0) {\n            tree[index] += lazy[index];\n            if (end != start) {\n                lazy[2 * index] += lazy[index];\n                lazy[2 * index + 1] += lazy[index];\n            }\n            \n            lazy[index] = 0;\n        }\n        // no overlap\n        if (end < l || start > r) {\n            return -1;\n        }\n        // completely overlap\n        if (l <= start && r >= end) {\n            return tree[index];\n        }\n        // partial overlap\n        int mid = start + (end - start) / 2;\n        return Math.max(queryUtil(l, r, start, mid, index * 2)\n                      , queryUtil(l, r, mid + 1, end, index * 2 + 1));\n    \n    }\n    \n    private void updateUtil(int l, int r, int start, int end, int index, int add) {\n        if (l > r || start > end) return;\n        if (lazy[index] != 0) {\n            tree[index] += lazy[index];\n            if (start != end) {\n                lazy[2 * index] += lazy[index];\n                lazy[2 * index + 1] += lazy[index];\n            }\n            \n            lazy[index] = 0;\n        }\n        // no-overlap\n        if (end < l || start > r) {\n            return;\n        }\n\t\t// update the current value and update the lazy array of the child\n        if (l <= start && r >= end) {\n            tree[index] += add;\n            if (start != end) {\n                lazy[2 * index + 1] += add;\n                lazy[2 * index] += add;\n            }\n            return;\n        }\n        \n        int mid = start + (end - start) / 2;\n        updateUtil(l, r, start, mid, index * 2, add);\n        updateUtil(l, r, mid + 1, end, index * 2 + 1, add);\n        tree[index] = Math.max(tree[index * 2], tree[index * 2 + 1]);\n    }\n}\n```
[]