'''
    Проверка скобочной последовательно на правильность
    Возвращает true, если последовательность правильная
    sequence - строка - скобочная последовательность
    i, j - границы проверки строки
'''
def isValidSequence(sequence:str, i:int, j:int):
    flag = 0                        # Реверсивный счетчик
    for k in range(i, j + 1):       # Проходим по строке от i до j включительно
        if (sequence[k] == '('):    # Если встречаем откр. скобку, увеличиваем счетчик
            flag += 1
        else:                       # Если встречаем закр. скобку, уменьшаем счетчик
            flag -= 1
        if flag < 0:                # Если счетчик < 0, дальнейшую проверку продолжать не имеет смысла - послед. неправильная
            return False
    return flag == 0


'''
    Восставновление скобочной последовательности с помощью проверок подстрок
    Возвращает входную скобочную последовательность
    sequence - входная строка - ПРАВИЛЬНАЯ скобочная последовательность
'''
def getSequence(sequence:str):
    output = [''] * len(sequence)   # Объявляем строку для восстановления проверки
    i = 0
    while i < len(sequence):    # Проходим по индексам исходной строки
        j = i + 1               # Начинаем проверку подстрок внутри входной строки с i и i+1
        while not isValidSequence(sequence, i, j) and j < len(sequence) and output[i] == '': # Выполняем проверку подстрок с увеличением j на 1 до тех пор,
            j += 1                                                                           # пока не найдем правильную последовательность (в границах i, j)
                                                                                             # или j < длины исходной строки
        if j < len(sequence) and output[i] == '':                                            # j выходит за границы в том случае, когда sequence[i] = ')'
            output[i] = '('                                              # В противном случае добавляем в строку внешние скоби по индексам i;j,
            output[j] = ')'                                              # образующих правильную последовательность
        i += 1
    output = ''.join(output)   # Преобразование массива символов в строку

    return output