Nhiều truy vấn successor và predecessor (Multiple Predecessor and Successor Queries)

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. Nếu một khóa xuất hiện nhiều lần, chỉ lần xuất hiện đầu tiên tạo nút; các lần sau bị bỏ qua.

Với mỗi giá trị truy vấn $x$, không yêu cầu $x$ phải tồn tại trong cây. Cần xác định hai khóa lân cận nghiêm ngặt theo giá trị:

• predecessor của $x$ là khóa lớn nhất $p$ trong cây thỏa $p<x$;
• successor của $x$ là khóa nhỏ nhất $s$ trong cây thỏa $s>x$.

Nếu một phía không có khóa thỏa điều kiện, kết quả phía đó là NONE.

Input

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

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

Dòng tiếp theo chứa số nguyên $q$ — số truy vấn.

$q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $x$.

Output

Với mỗi truy vấn, in một dòng gồm hai trường theo đúng thứ tự predecessor successor.

Nếu predecessor không tồn tại, trường thứ nhất là NONE. Nếu successor không tồn tại, trường thứ hai là NONE.

Subtask

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

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

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

Trong tất cả các subtask, mọi khóa và mọi giá trị truy vấn là số nguyên có dấu 64-bit.

Ví dụ

Input

7
8 3 10 1 6 14 4
3
6
1
9

Output

4 8
NONE 3
8 10

Giải thích

Với $x=6$, khóa lớn nhất nhỏ hơn $6$ là $4$ và khóa nhỏ nhất lớn hơn $6$ là $8$.

Với $x=1$, không có khóa nào nhỏ hơn $1$, còn successor là $3$, nên kết quả là NONE 3.

Với $x=9$, predecessor là $8$ và successor là $10$.