package main

import "fmt"

func main() {
    arr := []int{5, 2, 6, 1}
    ret := countSmaller(arr)
    fmt.Println(ret)
}

type Node struct {
    value int
    index int
}

func NewNode(v, i int) *Node {
    res := &Node{}
    res.value = v
    res.index = i
    return res
}

func countSmaller(nums []int) []int {
    ans := make([]int, 0)
    if len(nums) == 0 {
        return ans
    }
    for i := 0; i < len(nums); i++ {
        ans = append(ans, 0)
    }
    if len(nums) < 2 {
        return ans
    }
    arr := make([]*Node, len(nums))
    for i := 0; i < len(arr); i++ {
        arr[i] = NewNode(nums[i], i)
    }
    process(arr, 0, len(arr)-1, ans)
    return ans
}

func process(arr []*Node, l int, r int, ans []int) {
    if l == r {
        return
    }
    mid := l + ((r - l) >> 1)
    process(arr, l, mid, ans)
    process(arr, mid+1, r, ans)
    merge(arr, l, mid, r, ans)
}

func merge(arr []*Node, l int, m int, r int, ans []int) {
    help := make([]*Node, r-l+1)
    i := len(help) - 1
    p1 := m
    p2 := r
    for p1 >= l && p2 >= m+1 {
        if arr[p1].value > arr[p2].value {
            ans[arr[p1].index] = ans[arr[p1].index] + p2 - m
        }
        if arr[p1].value > arr[p2].value {
            help[i] = arr[p1]
            i--
            p1--
        } else {
            help[i] = arr[p2]
            i--
            p2--
        }
    }
    for p1 >= l {
        help[i] = arr[p1]
        p1--
        i--
    }
    for p2 >= m+1 {
        help[i] = arr[p2]
        p2--
        i--
    }
    for i := 0; i < len(help); i++ {
        arr[l+i] = help[i]
    }
}