#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define main dummy_main
int main( ) {
return 0 ;
}
#undef main
class Solution{
public :
string minRemoveToMakeValid( string s) {
int i;
int k = 0 ;
int N;
int mark[ 100000 ] = { } ;
string t;
string res;
N = s.size ( ) ;
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
if ( k == 0 && s[ i] == ')' ) {
continue ;
}
if ( s[ i] == '(' ) {
k++ ;
}
if ( s[ i] == ')' ) {
k-- ;
}
t + = s[ i] ;
}
N = t.size ( ) ;
for ( i= ( N) - 1 ; i>= ( 0 ) ; i-- ) {
if ( k > 0 && t[ i] == '(' ) {
k-- ;
mark[ i] = 1 ;
}
}
for ( i= ( 0 ) ; i< ( N) ; i++ ) {
if ( mark[ i] == 0 ) {
res + = t[ i] ;
}
}
return res;
}
}
;
// cLay varsion 20191102-1
// --- original code ---
// #define main dummy_main
// {}
// #undef main
//
//
// class Solution {
// public:
// string minRemoveToMakeValid(string s) {
// int i, k = 0, N;
// int mark[1d5] = {};
// string t, res;
//
// N = s.size();
// rep(i,N){
// if(k == 0 && s[i] == ')') continue;
// if(s[i]=='(') k++;
// if(s[i]==')') k--;
// t += s[i];
// }
// N = t.size();
//
// rrep(i,N) if(k > 0 && t[i] == '(') k--, mark[i] = 1;
// rep(i,N) if(mark[i]==0) res += t[i];
// return res;
// }
// };
I3ByYWdtYSBHQ0Mgb3B0aW1pemUgKCJPZmFzdCIpCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgbWFpbiBkdW1teV9tYWluCmludCBtYWluKCl7CiAgcmV0dXJuIDA7Cn0KI3VuZGVmIG1haW4KY2xhc3MgU29sdXRpb257CiAgcHVibGljOgogIHN0cmluZyBtaW5SZW1vdmVUb01ha2VWYWxpZChzdHJpbmcgcyl7CiAgICBpbnQgaTsKICAgIGludCBrID0gMDsKICAgIGludCBOOwogICAgaW50IG1hcmtbMTAwMDAwXSA9IHt9OwogICAgc3RyaW5nIHQ7CiAgICBzdHJpbmcgcmVzOwogICAgTiA9IHMuc2l6ZSgpOwogICAgZm9yKGk9KDApO2k8KE4pO2krKyl7CiAgICAgIGlmKGsgPT0gMCAmJiBzW2ldID09ICcpJyl7CiAgICAgICAgY29udGludWU7CiAgICAgIH0KICAgICAgaWYoc1tpXT09JygnKXsKICAgICAgICBrKys7CiAgICAgIH0KICAgICAgaWYoc1tpXT09JyknKXsKICAgICAgICBrLS07CiAgICAgIH0KICAgICAgdCArPSBzW2ldOwogICAgfQogICAgTiA9IHQuc2l6ZSgpOwogICAgZm9yKGk9KE4pLTE7aT49KDApO2ktLSl7CiAgICAgIGlmKGsgPiAwICYmIHRbaV0gPT0gJygnKXsKICAgICAgICBrLS07CiAgICAgICAgbWFya1tpXSA9IDE7CiAgICAgIH0KICAgIH0KICAgIGZvcihpPSgwKTtpPChOKTtpKyspewogICAgICBpZihtYXJrW2ldPT0wKXsKICAgICAgICByZXMgKz0gdFtpXTsKICAgICAgfQogICAgfQogICAgcmV0dXJuIHJlczsKICB9Cn0KOwovLyBjTGF5IHZhcnNpb24gMjAxOTExMDItMQoKLy8gLS0tIG9yaWdpbmFsIGNvZGUgLS0tCi8vICNkZWZpbmUgbWFpbiBkdW1teV9tYWluCi8vIHt9Ci8vICN1bmRlZiBtYWluCi8vIAovLyAKLy8gY2xhc3MgU29sdXRpb24gewovLyBwdWJsaWM6Ci8vICAgc3RyaW5nIG1pblJlbW92ZVRvTWFrZVZhbGlkKHN0cmluZyBzKSB7Ci8vICAgICBpbnQgaSwgayA9IDAsIE47Ci8vICAgICBpbnQgbWFya1sxZDVdID0ge307Ci8vICAgICBzdHJpbmcgdCwgcmVzOwovLyAKLy8gICAgIE4gPSBzLnNpemUoKTsKLy8gICAgIHJlcChpLE4pewovLyAgICAgICBpZihrID09IDAgJiYgc1tpXSA9PSAnKScpIGNvbnRpbnVlOwovLyAgICAgICBpZihzW2ldPT0nKCcpIGsrKzsKLy8gICAgICAgaWYoc1tpXT09JyknKSBrLS07Ci8vICAgICAgIHQgKz0gc1tpXTsKLy8gICAgIH0KLy8gICAgIE4gPSB0LnNpemUoKTsKLy8gCi8vICAgICBycmVwKGksTikgaWYoayA+IDAgJiYgdFtpXSA9PSAnKCcpIGstLSwgbWFya1tpXSA9IDE7Ci8vICAgICByZXAoaSxOKSBpZihtYXJrW2ldPT0wKSByZXMgKz0gdFtpXTsKLy8gICAgIHJldHVybiByZXM7Ci8vICAgfQovLyB9Owo=