#include #include using namespace std; int op_min(int a, int b){ return min(a, b); } int e_min(){ return (int)(1e9); } int op_max(int a, int b){ return max(a, b); } int e_max(){ return (int)(-1e9); } int main(){ int N; cin >> N; string S; cin >> S; S += '?'; N++; vectormax_r(N + 1); { vectorB(N + 1); for(int i = 0; i < N; i++){ B[i + 1] = B[i] + (S[i] == ')' ? -1 : 1); } atcoder::segtreeseg(B); for(int i = 0; i < N; i++){ auto judge = [&](int x){ return x >= B[i]; }; max_r[i] = seg.max_right(i, judge); } } vectormin_l(N + 1); { vectorB(N + 1); for(int i = 0; i < N; i++){ B[i + 1] = B[i] + (S[i] == '(' ? 1 : -1); } atcoder::segtreeseg(B); for(int i = 0; i < N; i++){ auto judge = [&](int x){ return x >= B[i]; }; min_l[i] = seg.min_left(i, judge); } } using Seg = atcoder::segtree; vector dp1(2, Seg(N + 1)); vector dp2(2, Seg(N + 1)); dp1[0].set(0,0); vector>del(N + 2); for(int i = 0; i < N; i++){ del[max_r[i]].push_back(i); } for(int r = 0; r < N; r++){ for(auto l: del[r]){ for(int j = 0; j < 2; j++){ dp1[j].set(l, e_max()); dp2[j].set(l, e_max()); } } int mx1 = max(dp1[r % 2].get(r), dp1[r % 2].prod(max(0, min_l[r] - 1), r) + 1); int mx2 = max(dp2[r % 2].get(r), dp2[r % 2].prod(min_l[r], r) + 1); if(S[r] != '(')dp1[(r + 1) % 2].set(r + 1, mx1); if(S[r] != ')')dp2[(r + 1) % 2].set(r + 1, max(mx1, mx2)); } cout << dp2[N % 2].get(N) << endl; return 0; }