// yukicoder: No.684 Prefix Parenthesis // 2019.7.9 bal4u #include #include #if 1 #define gc() getchar_unlocked() #else #define gc() getchar() #endif int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } void ins(char *s) { // 文字列の入力 スペース以下の文字で入力終了 do *s = gc(); while (*s++ > ' '); *(s-1) = 0; } typedef struct { int l, r, d; } T; T t[100005], s[100005]; int tz, sz; char S[100005]; int N; long long ans; int cmpt(const void *a, const void *b) { return ((T *)a)->r - ((T *)b)->r; } int cmps(const void *a, const void *b) { int t = ((T *)b)->d - ((T *)a)->d; if (t) return t; return ((T *)b)->l - ((T *)a)->l; } int main() { int i, l, r, ls, rs; N = in(), ins(S); l = r = ls = rs = 0; for (i = 0; i < N; i++) { if (S[i] == '(') l++; else { if (l) l--, ans += N-i; else r++; } if (r == 0) ls += l; else if (l == 0) rs += r; else if (l-r >= 0) t[tz].l = l, t[tz++].r = r; else s[sz].l = l, s[sz].r = r, s[sz++].d = l-r; } // printf("sz=%d, ans=%lld, ls=%d, rs=%d\n", sz, ans << 1, ls, rs); // for (i = 0; i < sz; i++) printf("%d(, %d)\n", t[i].l, t[i].r); qsort(t, tz, sizeof(T), cmpt); for (i = 0; i < tz; i++) { if (t[i].r <= ls) ans += t[i].r, ls -= t[i].r; else ans += ls, ls = 0; ls += t[i].l; } qsort(s, sz, sizeof(T), cmps); for (i = 0; i < sz; i++) { if (s[i].r <= ls) ans += s[i].r, ls -= s[i].r, s[i].r = 0; else ans += ls, s[i].r -= ls, ls = 0; ls += s[i].l; } ans += (ls <= rs)? ls: rs; printf("%lld\n", ans << 1); return 0; }