Solution is O(n^2). Note that `std::upper_bound`

is linear if the iterator is non-random-access (which happens when you use `std::list`

). Taking a look at the C++ reference:

The number of comparisons performed is logarithmic in the distance between first and last (At most log_{2}{(last - first)} + O(1) comparisons). **However, for non-RandomAccessIterators, the number of iterator increments is linear**.

Itâ€™s true that inserts in `std::list`

are O(1), but for that you have a bad trade-off. Try using `std::set`

instead, I believe it also has an upper bound method and O(log n) insert.