• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

فرزام می خواهد یک دنباله‌ی متوازن از پرانتزها را وارد رایانه‌ی جدید خود کند، اما او که به دلیل حساسیت پوستی به هوای آلوده تهران، همواره مجبور است از دستکش استفاده کند، در هنگام استفاده از کیبورد و تایپ کردن این دنباله مشکل دارد و گاهاً پرانتزها را جابه‌جا و یا اشتباه وارد می‌کند. قرار است به او کمک کنید تا حداقل تعداد پرانتزهایی را که باید تغییر کنند تا دنباله دوباره متوازن شود بیابد.

منظور از تغییر یک پرانتز عوض کردن ( با ) یا برعکس است.

دنباله‌ی متوازن به دنباله‌ای گفته می‌شود که تعداد ( ها و )ها در آن برابر باشد. همچنین در هر پیشوند از این دنباله، تعداد )ها حداقل به اندازه‌ی تعداد (ها باشد.

ورودی

یک رشته از پرانتزها به طول زوج، به طوری که طول آن حداکثر $10^5$ کاراکتر است.

خروجی

در تنها سطر از خروجی، حاقل تعداد پرانتزهایی که باید تغییر کنند تا دنباله متوازن شود را چاپ کنید.

مثال

ورودی نمونه ۱

())(

خروجی نمونه ۱

2

ورودی نمونه ۲

))()()((())(()))()()

خروجی نمونه ۲

1