34877번 - 그룹 부분 문자열과 쿼리 서브태스크

문제

'0'과 '1'만으로 이루어진 길이 1ドル$ 이상의 문자열 $A$가 다음 조건 중 하나를 만족하는 경우, 이러한 $A$를 그룹 문자열이라고 부릅니다.

• $A$에 '0'이 등장하지 않거나 '1'이 등장하지 않습니다.
• $A$에서 모든 '0'은 모든 '1'보다 먼저 등장합니다.
• $A$에서 모든 '1'은 모든 '0'보다 먼저 등장합니다.

예를 들어, "000", "11", "00111", "110"은 그룹 문자열이지만, "1011"이나 "00100"은 그룹 문자열이 아닙니다.

'0'과 '1'만으로 이루어진 문자열 $S$에 대해, $S$의 처음과 끝에서 문자를 원하는 만큼 지워 만들 수 있는 서로 다른 그룹 문자열의 개수를 $f(S)$라고 정의합니다. 예를 들어, $S$가 "10110"일 때 만들 수 있는 그룹 문자열은 "0", "01", "011", "1", "10", "11", "110"이 있습니다. 그러므로 $S$가 "10110"일 때 $f(S)$의 값은 7ドル$입니다. 이때 "10"이 $S$에 여러 번 등장하지만 $f(S)$를 구하는 데는 한 번만 세는 것에 유의하세요.

여러분에게 문자열 $X$에 대한 $Q$번의 질문이 주어집니다. 초기에 문자열 $X$는 빈 문자열입니다. 각 질문은 다음과 같은 형태입니다.

• $c$ $k$: 문자열 $X$의 끝에 문자 $c$를 $k$개 붙입니다. 그후 $f(X)$의 값을 구합니다.

이때 질문으로 문자열 $X$에 추가된 문자는 그다음 질문이 주어질 때에도 문자열 $X$에서 지워지지 않고 남아있습니다.

여러분은 각 질문에 대해 충분히 빨리 대답할 수 있을까요?

입력

첫 번째 줄에 정수 $Q$가 주어집니다.

두 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄에 질문에 대응되는 문자 $c_i$와 양의 정수 $k_i$가 주어집니다.

출력

$Q$개의 줄에 걸쳐 각 줄에 질문에 대한 정답을 출력합니다.

제한

• 1ドル \le Q \le 200,000円$
• 각 1ドル \le i \le Q$에 대해 $c_i$는 '0' 또는 '1'
• 각 1ドル \le i \le Q$에 대한 $k_i$의 합은 1ドル,000円,000円,000円$ 이하

서브태스크

노트

예제의 각 질문에 대해 새로운 문자열 $X$의 내용, 새롭게 만들 수 있는 그룹 문자열, 그리고 $f(X)$의 값은 다음과 같습니다.