숫자 앨범

쟈니는 숫자를 모으는 사람이다. 그는 큰 앨범에 숫자를 보관하는데, 새 숫자를 넣고 오래된 숫자를 지우면서 앨범을 계속 갱신한다.

이 앨범은 쟈니가 가장 아끼는 보물이라서, 누구도 숫자를 다른 숫자로 바꿔 놓지 못하기를 바란다. 그래서 그는 다음과 같이 정해지는 체크섬을 관리한다. 앨범의 숫자로 만들 수 있는 서로 다른 비어 있지 않은 부분 다중집합을 모두 구하고, 각 부분 다중집합의 최솟값을 찾은 뒤, 그 최솟값들의 산술 평균을 계산한다.

같은 숫자가 앨범에 여러 번 들어 있을 수 있으므로, 부분집합은 다중집합이다. 각 숫자는 부분 다중집합에 여러 번 들어갈 수 있지만, 앨범 전체에 있는 개수를 넘을 수는 없다. 두 다중집합은 모든 숫자의 개수가 같을 때만 같다. 예를 들어 앨범 $\{1, 2, 2, 5\}$에는 $\{1\}$, $\{1, 2\}$, $\{1, 2, 2\}$, $\{1, 2, 2, 5\}$, $\{1, 2, 5\}$, $\{1, 5\}$, $\{2\}$, $\{2, 2\}$, $\{2, 2, 5\}$, $\{2, 5\}$, $\{5\}$의 서로 다른 부분 다중집합 11개가 있다.

앨범은 자주 바뀌어서 체크섬을 손으로 계산하기는 번거롭다. 갱신 횟수와 각 연산을 읽고, 연산마다 체크섬을 구해 출력하는 프로그램을 작성하라.

첫 줄에는 갱신 횟수를 나타내는 양의 정수 $n$ ($1 \le n \le 250\,000$)이 주어진다. 이어지는 $n$개의 줄에는 각각 부호 + 또는 -, 공백 하나, 그리고 수 $a_i$ ($1 \le a_i \le 1\,000\,000\,000$)가 주어진다. +는 $a_i$를 앨범에 넣고, -는 앨범에 있는 $a_i$ 하나를 뺀다.

앨범은 처음에 비어 있다. 연산 후에는 항상 비어 있지 않으며, 앨범에 있는 숫자만 삭제된다.

정확히 $n$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 갱신 후의 체크섬을 출력한다. 각 체크섬에 대해 절대 오차 또는 상대 오차가 $10^{-6}$을 넘지 않으면 정답으로 인정한다.

첫 번째 샘플에서 모든 삽입이 끝난 후 앨범에는 $\{1, 2, 2, 5\}$가 들어 있다. 이때 쟈니가 고려하는 부분 다중집합은 위에서 나열한 11개이다. 이들의 최솟값은 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 5이다. 따라서 체크섬은 $\frac{19}{11}\approx 1.727272727$이다.