from typing import List
from typing import Set


def _reconstruct_mwis(weights: List[int], dp: List[int]) -> Set[int]:
    """
    Private helper function to reconstruct MWIS according to the optimal
    solution using backtracking.
    :param weights: list[int]
    :param dp: list[int]
    :return: set{int}
    """
    mwis = set()
    curr = len(dp) - 1
    while curr >= 2:
        if dp[curr - 1] >= dp[curr - 2] + weights[curr]:
            curr -= 1
        else:
            mwis.add(curr)
            curr -= 2
    if curr == 1:
        if weights[0] >= weights[1]:
            mwis.add(0)
        else:
            mwis.add(1)
    elif curr == 0:
        mwis.add(0)
    return mwis
    # Running time complexity: O(n)