Let us paint the largest \(N\) elements in \(A\) black and the rest white. (Ties are broken arbitrarily.)
If all pairs of parentheses corresponding each other matches black and white elements, the score will be \(\displaystyle (\sum_{i = N + 1}^{2N} A'_i) - ( \sum_{i = 1}^N A'_i)\), where \(A'\) is the result of sorting \(A\) in ascending order, which is obviously the maximum possible score.

It turns out that we can construct a parenthesis sequence that achieves it, as follows:

• Let \(S\) be the parenthesis sequence to construct.
• Maintain a stack \(a\), which is initially empty.
• For each \(i = 1, 2, 3, \dots, 2N\) in this order, do the following:
  • If \(a\) has an element of the color different from \(A_i\), pop one from \(a\), set the character in \(S\) at the position corresponding to the popped element to (, and set \(S_i\) to (.
  • Otherwise, push \(A_i\) to \(a\). (We postpone deciding \(S_i\).)

From the property of stack, a ( and a ) that are set at the same time will correspond to each other. Also, the two elements of \(A\) corresponding to such two parentheses obviously have different colors.
\(a\) will not contain white elements and black elements at the same time, so \(a\) will be empty in the end, since there are equal numbers of black and white elements.
Therefore, the procedure constructs a valid parenthesis sequence \(S\) that achieves the maximum possible score.