Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MEDQUERY - Dynamic Median

Yêu cầu:

Hãy quản lí một tập hợp các số nguyên không âm hỗ trợ các thao tác sau:

1. Thêm một phân tử

2. Xóa một phần tử

3. Tìm trung vị của tập hợp


Định nghĩa trung vị:

Trung vị của dãy a[1..N] được sắp xếp không giảm là phần tử a[(N+1)/2].


Input

Dòng đầu tiên chứa Q là số truy vấn. (1 <= Q <= 10^6)

Q dòng tiếp theo, mỗi dòng gồm một kí tự '+' hoặc '-' và một số nguyên không âm nhỏ hơn 10^9. Dấu '+' biểu thị thao tác thêm phần tử x vào tập hợp (có thể tập hợp đã có phần tử x nhưng thao tác này vẫn được thực hiện). Dấu '-' biểu thị thao tác xóa phần tử x khỏi tập hợp (bộ test đảm bảo tồn tại phần tử x trong tập hợp).


Output

Q dòng, mỗi dòng là trung vị của tập hợp sau mỗi thao tác thêm/xóa.


Sample


Input

Output

Explanation

20

+ 6

+ 2

+ 5

+ 3

+ 6

- 3

+ 8

- 6

- 5

+ 5

+ 2

- 8

+ 5

+ 5

- 2

+ 1

- 5

+ 4

+ 8

+ 7

6

2

5

3

5

5

6

5

6

5

5

2

5

5

5

5

5

4

5

5

[6]

[2, 6]

[2, 5, 6]

[2, 3, 5, 6]

[2, 3, 5, 6, 6]

[2, 5, 6, 6]

[2, 5, 6, 6, 8]

[2, 5, 6, 8]

[2, 6, 8]

[2, 5, 6, 8]

[2, 2, 5, 6, 8]

[2, 2, 5, 6]

[2, 2, 5, 5, 6]

[2, 2, 5, 5, 5, 6]

[2, 5, 5, 5, 6]

[1, 2, 5, 5, 5, 6]

[1, 2, 5, 5, 6]

[1, 2, 4, 5, 5, 6]

[1, 2, 4, 5, 5, 6, 8]

[1, 2, 4, 5, 5, 6, 7, 8]


Được gửi lên bởi:Le Anh Duc - A2K42 PBC
Ngày:2017-02-05
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED

hide comments
2017-11-19 14:08:20
Nếu không có phần tử nào ghi ra 0 -_-
2017-02-23 18:15:25 Lollipop
heap
2017-02-06 06:26:16
time 1s mà chưa thấy ai ac dưới 1s :V
phanduy16

Last edit: 2017-02-06 06:27:19
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.