Packing Bowls Two by Two

A potter packs bowls for shipping. Bowl i has diameter sizes[i]. One bowl may be set inside another when the outer diameter is at least factor times the inner one: outer >= factor * inner. Each packed set holds exactly two bowls: an outer bowl holds at most one bowl, and a bowl that sits inside another holds nothing. Every bowl is in at most one set; bowls left over travel alone.

Return the largest number of two-bowl sets that can be packed.

Examples

Input:  sizes = [1, 2, 3, 4], factor = 2
Output: 2
Explanation: 3 >= 2 * 1 and 4 >= 2 * 2. Pairing 1 with 2 first would leave 3 and 4 stuck.

Input:  sizes = [13, 4, 20, 6, 11, 10], factor = 2
Output: 3
Explanation: (4 in 11), (6 in 13), (10 in 20).

Input:  sizes = [7, 3, 3, 8, 1, 20], factor = 3
Output: 2
Explanation: for example (1 in 3) and (3 in 20); no third set exists.

Constraints

• 0 <= len(sizes) <= 10**5
• 1 <= sizes[i] <= 10**9, 1 <= factor <= 10
• A pair-by-pair search for partners (O(n^2)) will time out on the largest tests.

Goals

• Bound the answer first, then show the bound's natural pairing is optimal
• Match the small half against the large half with one forward scan