최근, 소들은 괄호의 균형이 맞는 문자열들을 가지고 최고의 하나만을 비교해왔었다.

문자열들은 다음과 같이 점수가 매겨진다 (모든 문자열들은 균형잡혀있다.) :

• ①문자열 "()" 은 1점; 만약 "A"가 점수 s(A)를 가진다면 "(A)"는 2*s(A)점을 가진다.
• ②"A"와 "B"가 각각 s(A), s(B)점이라면, "AB"는 s(A)+s(B)점이 된다.

예를 들어, s("(())()") = s("(())") + s("()") = 2*s("()")+1= 2*1+1 = 3이 된다.

암소 베시는 그녀를 따르는 모든 소들이 이기는 것을 원해서, 몇몇 문자열들의 점수 계산이 필요하다. 길이가 N (2 <= N <= 100,000)인 균형잡힌 문자열이 주어질 때, 베시를 도와 그 점수를 계산하자.

입력

• 첫번째 줄에는 N이 입력된다.
• 두번째 줄부터 N+1번째 줄까지는 1개의 정수가 입력된다. i번째 입력이 0이면 '('이고, 1이면 ')'이다. 입력예의 문자열은 "(())()" 이다.

출력

입출력 예

입력

6
0
0
1
1
0
1

출력

3

출처: USACO 2011 FEB SILVER
번역: pl0892029