// 二分搜索target右侧的下标
func bisectRight(arr []int, target int) int {
    l, r := 0, len(arr)
    for l < r {
        m := l + (r-l)>>1
        if arr[m] <= target {
            l = m+1
        } else {
            r = m
        }
    }
    return l
}

func findClosestElements(arr []int, k int, x int) []int {
  	// 找到右边界l，下标l及之前小于等于x
    l := bisectRight(arr, x) - 1
    // 下标r及之后大于x
    r := l+1
    cnt := 0
    n := len(arr)
    for cnt < k {
        cnt++
        if l < 0 {
            r++
        } else if r >= n || (x-arr[l]) <= (arr[r]-x) {
            // 此处可以不用绝对值，因为l所在必然小于等于x，r所在必然大于x
            l--
        } else {
            r++
        }
    }
    return arr[l+1:r]
}

// 归并排序
func MergeSort(arr []int, l, r int, less func(i, j int) bool) {
    if r-l <= 1 {
        return
    }
    m := l + (r-l)>>1
    MergeSort(arr, l, m, less)
    MergeSort(arr, m, r, less)
    Merge(arr, l, r, m, less)
}

func Merge(arr []int, l, r, m int, less func(i, j int) bool) {
    left := make([]int, m-l)
    right := make([]int, r-m)
    copy(left, arr[l:m])
    copy(right, arr[m:r])
    il, ir := 0, 0
    for i := l; i < r; i++ {
        if il >= len(left) {
            arr[i] = right[ir]
            ir++
        } else if ir >= len(right) || !less(right[ir], left[il]) {
            arr[i] = left[il]
            il++
        } else {
            arr[i] = right[ir]
            ir++
        }
    }
}

func abs(a, b int) int {
    if a > b {
        return a - b
    }
    return b - a
}

func findClosestElements(arr []int, k int, x int) []int {
    MergeSort(arr, 0, len(arr), func(i, j int) bool {
        return abs(i, x) < abs(j, x)
    })

    arr = arr[:k]
    sort.Ints(arr)
    return arr
}

type Item struct {
	idx     int
	val     int
	realVal int
}

type Heap struct {
	arr  []Item
	less func(i, j int) bool
	swap func(i, j int)
}

func (h *Heap) Sink() {
	n := 0
	for {
		l := n*2 + 1
		if l >= len(h.arr) {
			break
		}
		j := l
		r := l + 1
		if r < len(h.arr) && h.less(r, l) {
			j = r
		}
		if h.less(n, j) {
			break
		}
		h.swap(n, j)
		n = j
	}
}

func (h *Heap) Swim() {
	n := len(h.arr) - 1
	for {
		p := (n - 1) / 2
		if n == 0 || h.less(p, n) {
			break
		}
		h.swap(p, n)
		n = p
	}
}

func (h *Heap) Pop() Item {
	v := h.arr[0]
	h.swap(0, len(h.arr)-1)
	h.arr = h.arr[:len(h.arr)-1]
	h.Sink()
	return v
}

func (h *Heap) Push(v Item) {
	h.arr = append(h.arr, v)
	h.Swim()
}

func abs(a, b int) int {
	if a > b {
		return a - b
	}
	return b - a
}

func findClosestElements(arr []int, k int, x int) []int {
	h := &Heap{arr: make([]Item, 0)}
	h.less = func(i, j int) bool {
		// 先按绝对值从大到小排序，后按索引从大到小排序
		vi, vj := h.arr[i].val, h.arr[j].val
		ii, ij := h.arr[i].idx, h.arr[j].idx
		return vi > vj || vi == vj && ii > ij
	}
	h.swap = func(i, j int) {
		h.arr[i], h.arr[j] = h.arr[j], h.arr[i]
	}

	for i, v := range arr {
		// 将值放入大顶堆
		h.Push(Item{i, abs(v, x), v})
		// 当大顶堆的大小超过k时，表示数据条目溢出，可以把最大的（最不符合条件的）弹出
		if len(h.arr) > k {
			h.Pop()
		}
	}
	ans := make([]int, k)
	for i := 0; i < k; i++ {
		ans[i] = h.Pop().realVal
	}

	// 重新排序
	sort.Ints(ans)
	return ans
}