Cực đại hóa

Ban đầu bạn có một đa tập $S$ rỗng. Cần xử lý $Q$ truy vấn thuộc hai loại:

1. 1 x : thêm số nguyên dương $x$ vào $S$. Dữ liệu đảm bảo $x$ không nhỏ hơn bất kỳ phần tử nào đang có trong $S$, tức là các giá trị được thêm vào theo thứ tự không giảm.
2. 2 : chọn một tập con khác rỗng $s$ của $S$ sao cho giá trị

$$max(s)-avg(s)$$

là lớn nhất có thể, rồi in ra giá trị lớn nhất đó. Ở đây $max(s)$ là phần tử lớn nhất của $s$, còn $avg(s)$ là trung bình cộng các phần tử của $s$.

Vì $S$ là đa tập nên $s$ cũng là đa tập: một giá trị xuất hiện $c$ lần trong $S$ có thể được lấy tối đa $c$ lần vào $s$.

Truy vấn đầu tiên luôn thuộc loại 1, nên $S$ không bao giờ rỗng khi gặp truy vấn loại 2.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $Q$: số lượng truy vấn.
• $Q$ dòng tiếp theo, mỗi dòng mô tả một truy vấn: hoặc gồm hai số nguyên 1 x, hoặc gồm một số nguyên 2.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra trên một dòng riêng giá trị lớn nhất tìm được.

Đáp án được chấp nhận nếu sai số tuyệt đối hoặc sai số tương đối so với đáp án đúng không vượt quá ${10}^{-6}$.

Ràng buộc

• $1\le Q\le 5·{10}^5$
• $1\le x\le {10}^9$
• Mỗi giá trị được thêm vào không nhỏ hơn mọi giá trị đang có trong $S$.

Ví dụ