public class Solution {


    public class SegmentTreeNode {
        public int start, end;
        public int min;
        public SegmentTreeNode left, right;
        public SegmentTreeNode(int start, int end, int min) {
              this.start = start;
              this.end = end;
              this.min = min;
              this.left = this.right = null;
        }
     }

     public SegmentTreeNode build(int start, int end, int[] A) {
        if(start > end) {
            return null;
        }
        //叶节点
        if(start == end) {
            return new SegmentTreeNode(start, end, A[start]);
        }
        //递归构建子树
        int mid = (start + end) / 2;
        SegmentTreeNode root = new SegmentTreeNode(start, end, Integer.MAX_VALUE);
        root.left = build(start, mid, A);
        root.right = build(mid + 1, end, A);
        //更新该节点信息
        if(root.left != null) {
            root.min = Math.min(root.min, root.left.min);
        }
        if(root.right != null) {
            root.min = Math.min(root.min, root.right.min);
        }
        return root;
     }

     public int query(SegmentTreeNode root, int start, int end) {
        if(start <= root.start && root.end <= end) {
            return root.min;
        }
        int mid = (root.start + root.end) / 2;
        int ans = Integer.MAX_VALUE;
        //包括左区间
        if(start <= mid) {
            ans = Math.min(ans, query(root.left, start, end));
        }
        //包括右区间
        if(end > mid) {
            ans = Math.min(ans, query(root.right, start, end));
        }
        return ans;
     }

     public int [] business(int [] A, int k) {
         int [] ans = new int [A.length];

         SegmentTreeNode root = build(0, A.length - 1, A);
         for(int i = 0; i < A.length; i++) {
                int l = i - k;
                int r = i + k;
                if(l < 0) {
                    l = 0;
                }
                if(r > A.length - 1) {
                    r = A.length - 1;
                }
                int value = A[i] - query(root, l, r);
                ans[i] = value;
            }

         return ans;
     }
}