Call the goodness of a sequence of integers the bitwise OR of all its elements; the goodness of the empty sequence is 0.
Given an integer array arr, consider every strictly increasing subsequence of it: pick any indices i1 < i2 < ... < ik with arr[i1] < arr[i2] < ... < arr[ik] (k = 0 allowed, which gives the empty subsequence). Return all the different goodness values these subsequences can have, sorted ascending.
def distinct_goodness(arr: list[int]) -> list[int]
distinct_goodness([4, 2, 1, 6])
# [0, 1, 2, 4, 6, 7]
# []→0 [1]→1 [2]→2 [4]→4 [2,6]→6 [1,6]→7 ...
# 3 is impossible: it needs both 1 and 2, but 2 comes before 1
# and [1, 2] is not a subsequence in this order
distinct_goodness([3, 3, 3]) # [0, 3]
distinct_goodness([]) # [0]
Constraints: len(arr) <= 2000 and 0 <= arr[i] < 1024. There can be exponentially many increasing subsequences, so don't enumerate them; and an O(n²) pass over pairs of indices, each carrying a set of ORs, is also too slow at the top size.
Show hint
Every goodness value is below 1024. Keep best[g] = the smallest last element of any increasing subsequence seen so far whose OR is g (the empty one gives best[0] = -1). For each new element a, every g with best[g] < a can be extended, giving OR g | a ending in a. Keeping only the smallest ending value per OR is enough, because a smaller last element is never worse for extending later.