Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Tí và Tèo được nhận vào làm thêm tại một cửa hàng bánh piza. Nhiệm vụ của Tí là đóng gói, xếp bánh vào hộp cẩn thận, còn nhiệm vụ của Tèo là vận chuyển bánh theo địa chỉ yêu cầu của khách hàng.

Nhà bếp làm bánh liên tục, mỗi lần làm một chiếc bánh có kích thước khác nhau. Tí phải quản lý một hàng đợi những chiếc bánh piza. Tí luôn sắp xếp danh sách những chiếc bánh chờ được mang đi này theo thứ tự đường kính tăng dần. Mỗi lần có yêu cầu của khách hàng, Tí sẽ mang ra chiếc bánh có kích thước bằng phần tử trung vị trong tập hợp tất cả những chiếc bánh mà Tí hiện tại đang quản lý. Có nghĩa là nếu hiện tại Tí quản lý c cái bánh, nếu c lẻ, Tí sẽ mang đi chiếc bánh có kích thước lớn thứ (c+1)/2; trong trường hợp c chẵn, Tí sẽ lấy đi chiếc bánh có kích thước lớn thứ c/2+1.

Cửa hàng luôn ghi lại những hoạt động của mình, gồm mốc thời gian một chiếc bánh được ra lò và mốc thời gian có một chiếc bánh được chuyển đi. Với cách làm kì dị của Tí, cửa hàng này khá đau đầu trong việc liệt kê những chiếc bánh nào đã được xuất xưởng. Cho biết các mốc sự kiện xảy ra theo thời gian, các bạn hãy hãy giúp cửa hàng này lập ra danh sách những chiếc bánh đã được bán đi.

Input

Có 1 bộ test, gồm nhiều dòng, được thể hiện theo trình tự thời gian.

Mỗi dòng có thể là một số nguyên n, hoặc một kí tự ‘#’. Số nguyên dương n thể hiện tại thời điểm đó, một chiếc bánh piza có đường kính là n được làm xong và chuyển sang khâu đóng gói. Kí tự ‘#’ thể hiện tại thời điểm đó có yêu cầu của khách hàng, Tí sẽ mang cho Tèo một chiếc bánh piza để Tèo vận chuyển tới địa chỉ yêu cầu của khách hàng.

Số lượng bánh piza nhỏ hơn 10^6.

Output

In ra kích thước các chiếc bánh piza mà Tèo đã vận chuyển theo đúng thứ tự.

Example

Test 1:

Input:

1
2
3
4
#
#
#
#

Output:

3
2
4
1

Test 2:

Input:

1
#
2
#
3
#
4
#

Output:

1
2
3
4