## LCC/Moose '20 Contest 4 S3 - Deep Brackets

View as PDF

Points: 10 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Max loves balanced bracket sequences, and things that are deep. Thus, he decided to put the two together and create a deep bracket sequence. Unfortunately for him, the balanced bracket sequence he was given for his birthday is not very deep. Can you help him make it deeper? We define a flip to be an operation where you change a ( to a ) or vice versa. Max wants you to demonstrate the minimum number of flips he must execute to make his bracket sequence have depth at least . Note that the sequence may become unbalanced after the intermediate flips.

A bracket sequence is balanced if you can match every open bracket ( with a closed bracket ) that comes later in the sequence.

We define the depth of a bracket sequence to be the maximum number of nested bracket pairs. For example, the sequence ((()(()))) has depth because ((()(()))) is nested bracket pairs, and you cannot nest more than .

#### Input Specification

The first line of input contains an integer , is even, and .

The next line of input contains a balanced bracket sequence of length .

#### Output Specification

On one line, you are to output : the minimum number of flips you must make for the balanced bracket sequence to have depth at least .

On the next line, you are to output integers, the integer being the bracket you flip. If there are multiple solutions, you are to print the lexicographically least. If , this line is blank (still print a line though).

No further constraints.

#### Sample Input

10 5
((()))()()

#### Sample Output

4
4 5 7 9