Kệ sách

Bạn có một kệ sách và muốn đặt các cuốn sách lên đó. Bạn cần xử lý $q$ truy vấn thuộc ba loại:

1. L id — đặt cuốn sách có chỉ số $id$ vào bên trái của cuốn sách ngoài cùng bên trái hiện có.
2. R id — đặt cuốn sách có chỉ số $id$ vào bên phải của cuốn sách ngoài cùng bên phải hiện có.
3. ? id — tính số cuốn sách tối thiểu cần lấy ra khỏi kệ (từ đầu bên trái hoặc đầu bên phải) sao cho cuốn sách có chỉ số $id$ trở thành cuốn ngoài cùng bên trái hoặc ngoài cùng bên phải.

Cuốn sách đầu tiên được đặt lên kệ có thể ở vị trí bất kỳ (không quan trọng). Với mỗi truy vấn loại 3, đảm bảo cuốn sách $id$ đã có trên kệ. Các cuốn sách không được đặt trùng lặp, nên $id$ không lặp lại trong các truy vấn loại 1 và loại 2.

Lưu ý: sau khi trả lời một truy vấn loại 3, tất cả các cuốn sách vẫn nằm nguyên trên kệ và thứ tự tương đối giữa chúng không thay đổi (truy vấn loại 3 chỉ là câu hỏi giả định, không thực sự lấy sách ra).

Dữ liệu vào

• Dòng đầu chứa số nguyên $q$ là số truy vấn.
• $q$ dòng tiếp theo, mỗi dòng chứa một truy vấn theo đúng định dạng nêu trên.

Dữ liệu ra

Với mỗi truy vấn loại 3, in ra một dòng chứa đáp án tương ứng, theo thứ tự các truy vấn xuất hiện trong dữ liệu vào.

Ràng buộc

• $1\le q\le 2·{10}^5$
• $1\le id\le 2·{10}^5$
• Dữ liệu luôn hợp lệ: với truy vấn loại 3, cuốn sách $id$ chắc chắn đã có trên kệ; với truy vấn loại 1 và loại 2, cuốn sách $id$ chưa từng được đặt trước đó.
• Đảm bảo có ít nhất một truy vấn loại 3.

Ví dụ