시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 87 28 25 46.296%

문제

leejseo는 할 일 없는 크리스마스에 괄호 문자열을 가지고 놀고 있었다. 우연하게도 "(())"과 같은 문자열은 좌우 대칭의 형태를 가지고 있지만, 팰린드롬이 아니라는 것을 깨닫게 되었다. leejseo는 비록 이런 문자열이 팰린드롬은 아니지만, 나름대로 의미가 있다 생각했고, "(())", ")(", "(()())"과 같은 문자열을 대칭 문자열이라 부르기로 했다.

즉, 어떤 괄호 문자열('(' 또는 ')' 로만 이루어진 문자열)이 대칭 문자열임은 문자들의 순서를 거꾸로 한 후 '('와 ')'를 각각 ')'와 '('로 바꾼 결과가 자기 자신임을 의미한다. 예를 들어, "())(()"나 ")("는 대칭 문자열이며, "(("은 대칭 문자열이 아니다.

leejseo는 대칭 문자열 가운데 올바른 문자열에 더욱 관심이 많았다. 올바른 문자열은 다음과 같이 정의된다:

  • "()"은 올바른 문자열이다.
  • S가 올바른 문자열일 때, '('+S+')'도 올바른 문자열이다.
  • S와 T가 올바른 문자열일 때,  S+T도 올바른 문자열이다.
  • 이 외의 모든 문자열은 올바른 문자열이 아니다.

어떤 문자열이 올바른 문자열인 동시에 대칭 문자열이면 이 문자열은 leejseo를 편-안하게 만드니 편안한 문자열이라 부르자. 어떤 문자열의 부분 문자열이 편안한 문자열이라면, 편안한 부분 문자열이라 부르자. 단, 부분 문자열의 문자들은 원래의 문자열에서 서로 연속한 위치에 있어야 한다. 예를 들어, 문자열 "()()"가 있을 때, "(("는 "()()"의 부분 문자열이 아니며, "()()"의 1~2번째 문자로 구성된 부분 문자열과 3~4번째 문자로 구성된 부분 문자열은 모두 "()"이지만 다르게 취급한다.

괄호 문자열이 하나 주어졌을 때, 편안한 부분 문자열의 수를 구해보자.

입력

입력의 첫 줄에 길이가 1 이상 5,000 이하인 괄호 문자열 S가 주어진다.

출력

S의 편안한 부분 문자열의 수를 출력한다.

예제 입력 1

(()()))()

예제 출력 1

5

() 3개, ()() 1개, (()()) 1개로 총 5개의 편안한 부분 문자열이 있다.