시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 24 8 7 46.667%

문제

올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키파를 도와 올바른 괄호쌍이 되도록 고쳐 주자.

키파는 괄호를 입력할 때 매우 조심했기 때문에 한 번만 오타를 내었다. 올바른 괄호쌍은 다음과 같이 정의된다:

  • ()는 올바른 괄호쌍이다.
  • A가 올바른 괄호쌍이라면 (A) 또한 올바른 괄호쌍이다.
  • A와 B가 올바른 괄호쌍이라면 AB 또한 올바른 괄호쌍이다.

입력

첫째 줄에 키파가 입력한 괄호열이 주어진다. 길이는 1 이상 100,000 이하이다.

출력

첫째 줄에 하나의 문자만 고쳐서 올바른 괄호쌍이 될 수 있는 경우의 수를 출력한다.

예제 입력

()(())))

예제 출력

4

힌트

키파가 입력한 다음 문자열을 자세히 보자:

12345678
()(())))

2번째 문자 )를 (로 고침으로써 올바른 문자열을 만들 수 있다:

12345678
(((())))

비슷하게, 5번째 문자, 6번째 문자, 혹은 7번째 문자를 고침으로써 올바른 문자열을 만들 수 있다.