[Java Solution Using Segment Tree ]
Consider array arr[1,1,2,2,3,3,5] and k=2 and make an array grtrOrEq which stores at index i , index of least element greater than arr[i]+k . For example grtrOr
Consider array arr[1,1,2,2,3,3,5] and k=2 and make an array grtrOrEq which stores at index i , index of least element greater than arr[i]+k . For example grtrOrEq will look like [6, 6, 6, 6, 7, 7, 7]. Now make an array ans where at any index i ans[i]=grtrOrEq[i]-i.\nCode for grtrOrEq array\n```\nfor(int i=0;i<grtrOrEq.length;i++){\n   grtrOrEq[i]=grtrOrEq(arr,arr[i]+k);\n}\n```\n\nCode for function grtrOrEq\n```\npublic int grtrOrEq(long []arr,long k){\n    int l=-1;\n    int r=arr.length;\n    while(l+1<r){\n        int mid=(l+r)/2;\n        if(arr[mid]<=k){\n           l=mid;\n        }else{\n           r=mid;\n        }\n\t}\n    return r;\n}\n```\n\nCode for making ans array\n```\nfor(int i=0;i<n;i++){\n     ans[i]=grtrOrEq[i]-i;\n}\n```\n\nMake a class segment tree that has two functions build and query in which build preprocesses the segment tree and query finds maximum in some range.\nNow make a variable st of class Segment Tree and a variable sum\nNow for each index i sum is either\n1. Maximum of sum or ans[i] which means we are selecting two segments and they completely overlap\n2. Maximum of sum or ans[i]+maximum in ans from index grtrOrEq[i] to last index.\n\n```\nsegTree st=new segTree(n);\nst.build(0,0,n-1,ans);\nlong sum=0;\nfor(int i=0;i<n;i++){\n    sum=Math.max(ans[i],sum);\n    sum=Math.max(sum,ans[i]+st.query(0,0,n-1,grtrOrEq[i],n-1));\n}\n```\n\nCode for Segment Tree \n```\npublic class segTree {\n    private long[] seg;\n\n    public segTree(int size) {\n        seg = new long[4 * size];\n    }\n\n    // segment_index (0) ,low_for_arr (0), high_for_arr,arr (arr.length-1)\n    public void build(int ind, int low, int high, long[] arr) {\n       if (low == high) {\n           seg[ind] = arr[low];\n\t\t   return;\n\t\t}\n\t\tint mid = (low + high) / 2;\n\t\tbuild(2 * ind + 1, low, mid, arr);\n\t\tbuild(2 * ind + 2, mid + 1, high, arr);\n\t\tseg[ind] = mer(seg[2 * ind + 1], seg[2 * ind + 2]);\n\t}\n\n    // ind_for_seg (0) , low_for_arr (0) , high_for_arr (arr.length-1) , l=>given\n    // query left, r=>given query right\n    public long query(int ind, int low, int high, int l, int r) {\n       // NO OVERLAP\n       if (r < low || high < l) {\n           return Long.MIN_VALUE;\n       }\n       if (low >= l && high <= r) {\n           return seg[ind];\n       }\n       int mid = (low + high) / 2;\n       long left = query(2 * ind + 1, low, mid, l, r);\n       long right = query(2 * ind + 2, mid + 1, high, l, r);\n       return mer(left, right);\n\t }\n\n     public long mer(long left, long right) {\n         return Math.max(left, right);\n     }\n}\n```\n\n
['Tree', 'Binary Tree', 'Java']