Liệt kê khóa trong đoạn (Report BST Keys in a Range)

Nguồn: Phước Hưng OJ

Phiên bản: Phước Hưng OJ Extended

Đề bài

Dựng BST từ dãy $a_1,a_2,\ldots,a_n$ theo đúng thứ tự chèn. Khóa trùng bị bỏ qua.

Cho hai số nguyên $L$ và $R$. Nếu $L\le R$, hãy lấy tất cả các khóa $v$ đang có trong cây thỏa $L\le v\le R$ và in chúng theo thứ tự tăng dần.

Nếu $L>R$, đoạn cần xét được xem là rỗng nên không có khóa nào được chọn.

Input

Dòng đầu chứa số nguyên $n$.

Nếu $n>0$, dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$. Nếu $n=0$, dòng này không xuất hiện.

Dòng cuối chứa hai số nguyên $L$ và $R$.

Output

Nếu có ít nhất một khóa thuộc đoạn đóng $[L,R]$, in các khóa đó theo thứ tự tăng dần trên một dòng, cách nhau bởi một dấu cách.

Nếu không có khóa phù hợp hoặc $L>R$, in EMPTY.

Subtask

Subtask 1 (20 điểm): $0\le n\le 20$.

Subtask 2 (30 điểm): $0\le n\le 5000$.

Subtask 3 (50 điểm): $0\le n\le 200000$.

Trong tất cả các subtask, $a_i,L,R$ là số nguyên có dấu 64-bit. Khóa trùng bị bỏ qua khi dựng cây.

Ví dụ

Input

7
8 3 10 1 6 14 4
4 10

Output

4 6 8 10

Giải thích

Sau khi dựng cây, các khóa nằm trong đoạn đóng $[4,10]$ là $4,6,8,10$. Khi sắp theo thứ tự tăng dần, chúng xuất hiện đúng theo thứ tự 4 6 8 10.