open System
open System.Collections.Generic

module InputUtility =
    let InputTokens = new Queue<string>()

    let EnsureInput () =
        if InputTokens.Count = 0 then
            let input = Console.ReadLine ()
            let s = input.Split ([|' '|], StringSplitOptions.RemoveEmptyEntries)
            if s.Length > 0 then
                for x in s do InputTokens.Enqueue(x)
                true
            else false
        else true

    let rec ReadNext () =
        if EnsureInput () then InputTokens.Dequeue ()
        else ReadNext ()

    let ReadNextInt () = ReadNext () |> int

    let Read2Int () = ReadNextInt (), ReadNextInt ()

    let ReadListOf f n =
        let rec loop acc = function
            | 0 -> List.rev acc
            | c -> loop ((ReadNext () |> f) :: acc) (c-1)
        loop [] n

    let MultipleCaseWithId f =
        let caseNum = ReadNextInt ()
        let rec loop index =
            if index = caseNum then ()
            else
                f index
                loop (index + 1)
        loop 0

    let MultipleCase f = MultipleCaseWithId (fun _ -> f ())

    let ReadList n =
        let rec loop acc = function
            | 0 -> List.rev acc
            | c -> loop (ReadNext () :: acc) (c-1)
        loop [] n

open InputUtility

module ABC064 =
    type cacheMap<'a, 'b> = System.Collections.Generic.Dictionary<'a, 'b>

    let memoizeMap (dict:cacheMap<_, _>) f =
        fun n ->
            match dict.TryGetValue n with
            | (true, v) -> v
            | _ ->
                let temp = f(n)
                dict.Add(n, temp)
                temp

    let memoize f = memoizeMap (new cacheMap<_, _> ()) f

    let private Insertion () =
        let n = ReadNextInt ()
        let s = ReadNext ()
        let oo = System.Int32.MaxValue / 2
        let lc, rc = '(', ')'
        let rec cal = memoize (fun (i, c, b) ->
            match b with
            | 0 ->
                let ar = if c >= n then oo else 1 + cal (i, c + 1, 0)
                let nr = cal (i, c, 1)
                min ar nr
            | 1 ->
                if s.[i] = lc then cal (i, c + 1, 2)
                elif c = 0 then oo else cal (i, c - 1, 2)
            | _ ->
                if i + 1 = n then c
                else
                    let nr = cal (i + 1, c, 0)
                    let ar = if c = 0 then oo else 1 + cal (i, c - 1, 2)
                    min ar nr)
        let rec get acc r i c = function
            | 0 ->
                if c < n && r = 1 + cal (i, c + 1, 0) then
                    get (lc :: acc) (r - 1) i (c + 1) 0 
                else
                    get acc r i c 1
            | 1 ->
                if s.[i] = lc then
                    get (lc :: acc) r i (c + 1) 2
                else
                    get (rc :: acc) r i (c - 1) 2
            | _ ->
                if i + 1 = n then
                    let ra = List.replicate r rc @ acc |> List.rev
                    System.String.Join ("", ra)
                else
                    if r = cal (i + 1, c, 0) then
                        get acc r (i + 1) c 0
                    else
                        get (rc :: acc) (r - 1) i (c - 1) 2
        let minR = cal (0, 0, 0)
        //printfn "minR = %d" minR
        get [] minR 0 0 0 |> printfn "%s"

    let Entry = Insertion

ABC064.Entry ()

Measured memory_bytes: 23232