+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- دانشجویی یک رشته از پرانتزها پیدا کرده است. او می‌داند یک پرانتزگذاری درست به شکل زیر است: + $()$ یک پرانتزگذاری صحیح است. + اگر $S$ یک پرانتزگذاری صحیح باشد، $(S)$ هم یک پرانتزگذاری درست است. + اگر $S$ و $T$ یک پرانتزگذاری درست باشد، $TS$ که از کنار هم گذاشتن آن دو رشته به دست می‌آید نیز پرانتزگذاری صحیح است. همچنین یک شیفت دوری به اندازه‌ی $k$ روی رشته‌ی $S$ باعث تبدیل شدن آن به رشته‌ی $T$ می‌شود که داریم: $$\forall \,0 \leq i \lt |S|, \quad T[i] = S[(i + k) mod |S|]$$ خوشحالی دانشجو برابر تعداد $k$های کوچکتر از طول رشته ورودی است که شیفت های دوری رشته پیدا شده به اندازه $k$، پرانتزگذاری درست باشد. این تعداد را پیدا کرده و به دانشجو اعلام کنید تا آن مقدار خوشحال شود. # ورودی در خط اول ورودی عدد $n$ که طول رشته است آمده است. در خط دوم ورودی رشته‌ی $S$ شامل کاراکتر های `)` و `(` است می‌آید. # خروجی در تنها خط خروجی خوشحالی دانشجو معادل تعداد شیفت‌های دوری از رشته که پرانتزگذاری صحیح هستند را چاپ کنید. # مثال‌ها ## ورودی نمونه ۱ ``` 6 ))()(( ``` ## خروجی نمونه ۱ ``` 2 ``` ## ورودی نمونه ۲ ``` 6 ())((( ``` ## خروجی نمونه ۲ ``` 0 ```