ფრჩხილების ჩამატება

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

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

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

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


მილჰაუსს სჭირდება დახმარება სასკოლო დავალების შესრულებაში. მისი ამოცანა ასეთია:

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

·         ცარიელი სტრიქონი გამართულია;

·         თუ  S არის გამართული სტრიქონი, მაშინ ( S ) ასევე გამართულია;

·         თუ s და t გამართული სტრიქონებია, მაშინ მათი გაერთიანება, st , ასევე გამართულია;

მაგალითად, "(()())", "" და "(())()" გამართული სტრიქონებია და "())(" ,  "()(" და ")" გაუმართავი, შესასწორებელი.

შესატანი მონაცემები:  ფრჩხილებისაგან შემდგარი მიმდევრობა, სიმბოლოების რაოდენობა n - (1<= n <=50).

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




მაგალითები

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