Upper bound: first index past a value

Write upper_bound(a: list[int], x: int) -> int that returns the first index i with a[i] > x. If no element is larger than x, return len(a). a is sorted in non-decreasing order and may contain duplicates.

It's the position where x would be inserted to keep a sorted, after any values equal to x. Together with lower bound, upper_bound(a, x) - lower_bound(a, x) counts the copies of x.

a = [2, 4, 4, 4, 9]
upper_bound(a, 4)    # 4   (9 is the first value > 4)
upper_bound(a, 5)    # 4
upper_bound(a, 1)    # 0
upper_bound(a, 9)    # 5   (= len(a))

• 0 <= len(a) <= 10^6; the tests make thousands of calls on one big list, so it must be O(log n).
• Don't use the bisect module or list.index; write the loop.
• C++ / Java: you write upperBoundAll(a, xs), which returns upper_bound(a, x) for every x in xs, in order, so the tests can run many searches on one big list. Write upperBound as a helper and call it in a loop.

Decide what lo and hi mean before you write it: for example, keep the answer inside the half-open range [lo, hi). The only difference from lower bound is whether an element equal to x sends you left or right.