Xóa nút trong BST (Delete Node in a BST)

Nguồn: LeetCode

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

Đề bài

Dựng một BST từ $n$ khóa phân biệt $a_1,a_2,\ldots,a_n$ theo đúng thứ tự chèn. Sau đó cần xóa khóa key.

Nếu key không tồn tại, cây giữ nguyên. Nếu nút cần xóa tồn tại:

• nút không có con được loại bỏ trực tiếp;
• nút có đúng một con được thay bằng nút con duy nhất;
• nút có hai con phải được thay bằng inorder successor, tức nút có khóa nhỏ nhất trong cây con phải. Sau đó xóa nút successor ở vị trí cũ.

Quy ước successor ở trường hợp hai con được dùng để cấu trúc cây sau khi xóa là duy nhất trong phiên bản này.

Hãy in preorder của BST sau thao tác.

Input

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

Nếu $n>0$, dòng tiếp theo chứa $n$ khóa phân biệt $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 số nguyên key — khóa cần xóa.

Output

Nếu cây sau thao tác không rỗng, in preorder trên một dòng, các khóa cách nhau bởi một dấu cách.

Nếu cây rỗng, in EMPTY.

Subtask

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

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

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

Trong tất cả các subtask, các khóa của cây phân biệt và $-10^5\le a_i,\text{key}\le 10^5$.

Ví dụ

Input

7
5 3 6 2 4 7 1
3

Output

5 4 2 1 6 7

Giải thích

Trong cây ban đầu, nút $3$ có hai con với hai cây con chứa các khóa $\{2,1\}$ và $\{4\}$. Khóa nhỏ nhất trong cây con phải của $3$ là $4$, nên $4$ được dùng làm inorder successor.

Sau khi thay $3$ bằng $4$ và xóa vị trí cũ của $4$, preorder của cây là 5 4 2 1 6 7.