Where Heapsort Spends Its Swaps

Heapsort has two phases, and they do not cost the same. Count the swaps each performs, on the array as this procedure leaves it:

• build — Floyd's bottom-up heapify, counting every swap a sift-down makes;
• extract — for end from n - 1 down to 1: swap a[0] with a[end] (always counted, even when end holds the same value), then sift down within the first end items, counting those swaps too.

Write heapsort_swaps(nums) returning the pair (build_swaps, extract_swaps).

Examples

Input:  nums = [4, 10, 3, 5, 1]
Output: (2, 7)

Input:  nums = [1, 2, 3, 4, 5, 6, 7]
Output: (4, 12)

Constraints

• 0 <= len(nums) <= 10**5, values are integers
• An empty list and a one-item list both cost (0, 0).

Goals

• Count the two phases of heapsort separately
• See the linear build next to the n log n extraction
• Instrument an algorithm without changing what it computes