Bộ lặp cây tìm kiếm nhị phân (Binary Search Tree Iterator)

Nguồn: LeetCode

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

Đề bài

Dựng BST từ $n$ khóa phân biệt $a_1,a_2,\ldots,a_n$ theo đúng thứ tự chèn. Xét dãy inorder của cây, tức các khóa theo thứ tự trái - gốc - phải.

Một bộ lặp (iterator) được đặt ban đầu ở vị trí trước phần tử đầu tiên của dãy inorder. Sau đó xử lý $q$ lệnh theo đúng thứ tự:

N tương ứng với next(): di chuyển bộ lặp tới phần tử kế tiếp trong dãy inorder và in khóa tại vị trí mới.

H tương ứng với hasNext(): kiểm tra có còn phần tử nào ở sau vị trí hiện tại hay không. Lệnh này không làm thay đổi vị trí bộ lặp.

Mọi lệnh N trong input được bảo đảm hợp lệ, nghĩa là khi lệnh đó xuất hiện luôn còn ít nhất một phần tử kế tiếp.

Input

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

Dòng thứ hai chứa $n$ khóa phân biệt $a_1,a_2,\ldots,a_n$ theo thứ tự chèn.

Dòng thứ ba chứa số nguyên $q$.

$q$ dòng tiếp theo, mỗi dòng chứa đúng một ký tự N hoặc H.

Output

Mỗi lệnh tạo đúng một dòng output.

Với N, in khóa được trả về bởi next().

Với H, in true nếu còn phần tử kế tiếp; ngược lại in false. Hai từ khóa này được viết bằng chữ thường đúng như trên.

Subtask

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

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

Subtask 3 (50 điểm): $1\le n,q\le 10^5$.

Trong tất cả các subtask, $0\le a_i\le 10^6$, các $a_i$ phân biệt và mọi lệnh N đều hợp lệ.

Ví dụ

Input

5
7 3 15 9 20
10
N
N
H
N
H
N
H
N
H
H

Output

3
7
true
9
true
15
true
20
false
false

Giải thích

Dãy inorder của cây là $3,7,9,15,20$. Hai lệnh N đầu tiên lần lượt đưa bộ lặp tới $3$ rồi $7$.

Sau $7$ vẫn còn phần tử nên lệnh H in true. Các lệnh N tiếp theo lần lượt trả $9$, $15$ và $20$. Sau khi bộ lặp đã ở $20$, không còn phần tử phía sau, nên hai lệnh H cuối đều in false; việc gọi H không làm thay đổi vị trí.