27515번 - 1차원 2048과 쿼리

$2^k$ ($0 \le k \le 62$) 꼴의 정수 또는 $0$으로만 이루어진 수열이 있습니다. 흐즈로는 이 수열에 대해 다음과 같은 연산을 정의했습니다.

• $a_i = a_j$ 인 서로 다른 $i$, $j$를 골라서 $a_i, a_j$를 각각 $2a_i, 0$으로 변경합니다. (이때, 수열의 첫 번째 원소는 $a_1$입니다.)

예를 들어, 수열 $[2, 4, 2, 0, 1]$에 $i=1, j=3$을 골라 실행한다면 수열은 $[4, 4, 0, 0, 1]$이 되며, 여기에 $i=1, j=2$를 골라 실행한다면 수열은 $[8, 0, 0, 0, 1]$이 됩니다.

흐즈로는 수열에 연산을 여러 번 실행하여 수열의 최댓값이 가능한 한 커지길 원하지만, 수열 전체에 이 연산을 계속 반복했다가는 머리가 아파질 것이라고 생각하였습니다.

그러던 중 흐즈로는 더욱 골치 아픈 문제점을 생각하였습니다. 수열이 바뀌면 연산을 처음부터 다시 시작해야 한다는 것입니다!

여러분이 해결해야 할 문제는 다음과 같습니다. 우선 초기의 수열 $a$는 빈 수열 $[]$으로 정의합니다. 그 후 다음과 같은 종류의 쿼리가 총 $Q$개 주어집니다.

• $+x$ : $a$의 끝에 $x$를 추가합니다. 그 뒤 수열에 흐즈로가 정의한 연산을 $0$번 이상 수행해 만들 수 있는 가장 큰 최댓값을 출력합니다. $x$는 $1$ 이상의 $2$의 거듭제곱 또는 $0$임이 보장됩니다.
• $-x$ : $a$에 마지막으로 등장하는 $x$를 제거합니다. 그 뒤 수열에 흐즈로가 정의한 연산을 $0$번 이상 수행해 만들 수 있는 가장 큰 최댓값을 출력합니다. $x$는 $1$ 이상의 $2$의 거듭제곱 또는 $0$임이 보장되며, $a$에는 $x$가 적어도 하나 이상 존재함이 보장됩니다.

흐즈로는 이미 머리가 너무 아파서 문제에 대해 생각할 정신조차 없습니다. 흐즈로를 도와 문제를 해결해 주세요!

첫 번째 줄에 쿼리의 개수 $Q$ ($1 \le Q \le 10^6$)가 주어집니다.

두 번째 줄부터 $Q+1$ 번째 줄까지 쿼리가 주어집니다. 각 쿼리는 $+x$ 또는 $-x$ ($x$는 $0$ 또는 $2^k$ $(0 \le k \le 62)$) 중 하나이며, $-x$의 경우 수열 $a$에 $x$가 적어도 하나 이상 존재함이 보장됩니다.

입력의 양이 많기 때문에 언어에 따른 빠른 입출력 방법을 사용할 것을 권장합니다. 빠른 입출력 방법은 15552: 빠른 A+B를 참고하세요.

$Q$개의 쿼리에 대해 각각 한 줄에 문제의 정답을 출력하세요. $a$가 빈 수열인 경우 문제의 정답은 $0$으로 간주합니다. 모든 쿼리에 대해 문제의 정답이 $2^{62}$보다 크지 않음이 보장됩니다.