When the Clever Sort Finally Wins

A library has to choose between two sorts for every call. On n items

• insertion sort costs a * n * (n - 1) // 2 comparisons;
• merge sort costs b * n * ceil_log2(n) comparisons, where ceil_log2(n) is the number of halvings needed to get from n down to 1, so ceil_log2(1) = 0, ceil_log2(2) = 1, ceil_log2(5) = 3.

Write sort_crossover(a, b, limit) returning the smallest n in 1 .. limit at which merge sort makes strictly fewer comparisons than insertion sort, or -1 if it never does within that range.

Examples

Input:  a = 1, b = 1, limit = 100
Output: 10
Explanation: at n = 9 both sorts cost 36 comparisons; at n = 10 merge sort costs 40 against 45.

Input:  a = 1, b = 50, limit = 10
Output: -1
Explanation: a merge sort this expensive has not caught up by n = 10.

Constraints

• 1 <= a <= 10**9, 1 <= b <= 10**9, 1 <= limit <= 10**18
• Evaluating every n is far too slow; the comparison flips at most once as n grows.

Goals

• See that an asymptotically better algorithm can lose on small inputs
• Find the crossing point of two cost functions without evaluating every size
• Binary search a predicate that flips exactly once