დაბალანსება

დროის ლიმიტი: 2 წმ

მეხსიერების ლიმიტი: 512 მეგაბაიტი

შემავალი მონაცემები: cin

გამომავალი მონაცემები: cout


ბესიმ ახლახანს შეიძინა ახალი პტოპი, მაგრამ საუბედუროდ, პატარა კლავიატურაზე დიდი ჩლიქებით ბეჭდვას კარგად ვერ ახერხებს. ბესის საყვარელი გასართობია ბალანსირებულფრჩხილებიანი სტრიქონების შექმნა, არადა, იცის, რომ სტრიქონში თუნდაც ერთი სიმბოლოს არასწორად დაწერა ბალანსის დარღვევას იწვევს. ბესისთვის მნიშვნელოვანია მოცემულ სტრიქონში ისეთი ფრჩხილის პოვნა, რომლის საპირისპიროთი შეცვლაც (რევერსირება) საკმარისია იმისათვის, რომ სტრიქონი დაბალანსებულად გადაიქცეს.

დაეხმარეთ ბესის, რომ მოცემულ სტრიქონში დაითვალოს ისეთი ფრჩხილების რაოდენობა, რომლებსაც აქვთ ზემოაღნიშნული თვისება (მხოლოდ ამ ერთი ფრჩხილის რევერსირება სტრიქონს გადააქცევს დაბალანსებულად).

რამდენიმე გზაა იმისათვის, რომ დავადგინოთ, არის თუ არა სტრიქონი დაბალანსებული. ალბათ, ყველაზე მარტივია, როცა ვადარებთ გახსნილი და დახურული ფრჩხილების რაოდენობას. აუცილებელია, რომ გახსნილი და დახურული ფრჩხილების რაოდენობა იყოს თანაბარი. მაგალითად ქვემოთ მოცემული სტრიქონები დაბალანსებულია:

()

(())

()(()())

მაგრამ ეს პირობა საკმარისი არ არის, მაგალითად ქვემოთ მოცემული სტრიქონები არ არის დაბალანსებული:

)(

())(

((())))

 

შეტანის ფორმატი:

* სტრიქონი 1: ფრჩხილებისაგან შედგენილი სტრიქონი სიგრძით N (1 <= N <= 100,000).

 

გამოტანის ფორმატი:

* სტრიქონი 1: ისეთი ფრჩხილების რაოდენობა, რომლის რევერსირება სტრიქონს გადააქცევს დაბალანსებულად.




მაგალითები

შესატანი მონაცემები
()(()))) დაკოპირება
გამოსატანი მონაცემები
4 დაკოპირება

შენიშვნა

სტრიქონის ფრჩხილები გადავნომროთ:

1 2 3 4 5 6 7 8
( ) ( ( ) ) ) )

ადვილი შესამჩნეია, რომ მე-2 პოზიციაზე მდგომი ფრჩხილის რევერსირება მოცემულ სტრიქონს დაბალანსებულად გადააქცევს.

1 2 3 4 5 6 7 8
( ( ( ( ) ) ) )

იგივე თვისება აქვთ ფრჩხილებს, რომლებიც დგანან მე-5, მე-6 და მე-7 პოზიციებზე. ანუ, სულ ასეთი თვისების მქონე ფრჩხილი არის 4 ცალი.