package main

import "fmt"

func main() {
    ret := nums2(5, 4, 7)
    fmt.Println(ret)
}

func nums2(n, l, r int) int {
    allMap := make(map[int]int)
    return dp(n, l, r, allMap)
}

func size(n int) int {
    if n == 1 || n == 0 {
        return 1
    } else {
        half := size(n / 2)
        return (half << 1) + 1
    }
}

func dp(n, l, r int, allMap map[int]int) int {
    if n == 1 || n == 0 {
        return twoSelectOne(n == 1, 1, 0)
    }
    half := size(n / 2)
    all := (half << 1) + 1
    mid := n & 1
    if l == 1 && r >= all {
        if _, ok := allMap[n]; ok {
            return allMap[n]
        } else {
            count := dp(n/2, 1, half, allMap)
            ans := (count << 1) + mid
            allMap[n] = ans
            return ans
        }
    } else {
        mid = twoSelectOne((l > half+1 || r < half+1), 0, mid)
        left := twoSelectOne(l > half, 0, dp(n/2, l, getMin(half, r), allMap))
        right := twoSelectOne(r > half+1, dp(n/2, getMax(l-half-1, 1), r-half-1, allMap), 0)
        return left + mid + right
    }
}

func twoSelectOne(c bool, a, b int) int {
    if c {
        return a
    } else {
        return b
    }
}

func getMax(a, b int) int {
    if a > b {
        return a
    } else {
        return b
    }
}

func getMin(a, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}