Xóa nút có hai con (Delete a Two-Child Node from a BST)

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 khóa $x$ được bảo đảm tồn tại và nút mang khóa $x$ có đúng hai con. Để kết quả của thao tác xóa được xác định duy nhất, bắt buộc dùng inorder successor của $x$: đó là nút có khóa nhỏ nhất trong cây con phải của $x$.

Thay khóa tại vị trí của $x$ bằng khóa của successor, sau đó xóa nút successor ở vị trí cũ của nó. Cây sau thao tác vẫn phải là một BST.

Hãy in preorder của cây sau khi xóa.

Input

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

Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ theo thứ tự chèn.

Dòng thứ ba chứa khóa $x$ cần xóa.

Output

In các khóa của cây sau thao tác xóa theo preorder, các khóa cách nhau bởi một dấu cách.

Subtask

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

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

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

Trong tất cả các subtask, $a_i$ và $x$ là số nguyên có dấu 64-bit; khóa trùng bị bỏ qua khi dựng cây; $x$ tồn tại và nút mang khóa $x$ có đúng $2$ con.

Ví dụ

Input

7
8 3 10 1 6 14 4
3

Output

8 4 1 6 10 14

Giải thích

Nút $3$ có hai con. Cây con phải của $3$ có các khóa $6$ và $4$, trong đó khóa nhỏ nhất là $4$, nên $4$ là inorder successor của $3$.

Khóa $4$ thay thế vị trí của $3$, rồi nút $4$ cũ được xóa. Preorder của cây kết quả là 8 4 1 6 10 14.