func lexicalOrder(n int) []int {
	res := make([]int, n)
	if n == 0 {
		return res
	}
	res[0] = 1
	for i := 1; i < n; i++ {
		if pre := res[i-1]; pre*10 <= n {
			res[i] = pre * 10
		} else if pre != n && pre%10 != 9 {
			res[i] = pre + 1
		} else {
			for res[i] = pre / 10; res[i]%10 == 9; res[i] /= 10 {
			}
			res[i]++
		}
	}
	return res
}

type ints []int

func (is ints) Len() int           { return len(is) }
func (is ints) Less(i, j int) bool { return strconv.Itoa(is[i]) < strconv.Itoa(is[j]) }
func (is ints) Swap(i, j int)      { is[i], is[j] = is[j], is[i] }

func lexicalOrderSort(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = i + 1
	}
	sort.Sort(ints(res))
	return res
}