import std.conv, std.functional, std.stdio, std.string; import std.algorithm, std.array, std.bigint, std.container, std.math, std.numeric, std.range, std.regex, std.typecons; import core.bitop; class EOFException : Throwable { this() { super("EOF"); } } string[] tokens; string readToken() { for (; tokens.empty; ) { if (stdin.eof) { throw new EOFException; } tokens = readln.split; } auto token = tokens.front; tokens.popFront; return token; } int readInt() { return readToken.to!int; } long readLong() { return readToken.to!long; } real readReal() { return readToken.to!real; } bool chmin(T)(ref T t, in T f) { if (t > f) { t = f; return true; } else { return false; } } bool chmax(T)(ref T t, in T f) { if (t < f) { t = f; return true; } else { return false; } } int binarySearch(alias pred, T)(in T[] as) { int lo = -1, hi = cast(int)(as.length); for (; lo + 1 < hi; ) { const mid = (lo + hi) >> 1; (unaryFun!pred(as[mid]) ? hi : lo) = mid; } return hi; } int lowerBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a >= val)); } int upperBound(T)(in T[] as, T val) { return as.binarySearch!(a => (a > val)); } int N; string S; void main() { /* int opt = -1; int[][][] ps; { // auto p = [[3, 1], [4, 1], [5, 9], [2, 1]]; auto p = [[3, 1], [4, 1], [5, 9], [1, 2]]; p.sort; do { int score; int[] a = [0, 0]; foreach (b; p) { if (a[1] <= b[0]) { score += a[1]; a = [a[0] + (b[0] - a[1]), b[1]]; } else { score += b[0]; a = [a[0], (a[1] - b[0]) + b[1]]; } } if (chmax(opt, score)) { ps = []; } if (opt == score) { ps ~= p.dup; } } while (p.nextPermutation); } writeln(opt); foreach (p; ps) { writeln(p); } return; //*/ try { for (; ; ) { N = readInt(); S = readToken(); long ans; alias Entry = Tuple!(int, int); Entry[] es; Entry e; int cnt; foreach (c; S) { switch (c) { case '(': { ++e[1]; } break; case ')': { if (e[1] > 0) { ++cnt; --e[1]; } else { ++e[0]; } } break; default: assert(false); } ans += cnt; es ~= e; } debug { writeln("es = ", es); } es.sort!((a, b) => ([sgn(a[0] - a[1]), a[0]] < [sgn(b[0] - b[1]), b[0]])); debug { writeln("es = ", es); } Entry f; foreach (i; 0 .. N) { const t = min(f[1], es[i][0]); ans += t; f = tuple(f[0] + (es[i][0] - t), (f[1] - t) + es[i][1]); } ans *= 2; writeln(ans); } } catch (EOFException e) { } }