Tổ tiên chung gần nhất trong BST (Lowest Common Ancestor of a Binary Search Tree)

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.

Cho hai khóa khác nhau $p$ và $q$, cả hai đều tồn tại trong cây. Một nút $u$ là tổ tiên chung của $p$ và $q$ nếu cả hai nút mang khóa $p$ và $q$ đều nằm trong cây con gốc tại $u$. Theo quy ước, một nút được xem là hậu duệ của chính nó.

Tổ tiên chung gần nhất (Lowest Common Ancestor - LCA) là tổ tiên chung có độ sâu lớn nhất, tức nằm thấp nhất trong cây.

Hãy in khóa của LCA của hai nút mang khóa $p$ và $q$.

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 hai khóa $p$ và $q$.

Output

In một số nguyên là khóa của tổ tiên chung gần nhất của $p$ và $q$.

Subtask

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

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

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

Trong tất cả các subtask, $-10^9\le a_i,p,q\le 10^9$; các $a_i$ phân biệt; $p\ne q$ và cả $p,q$ đều xuất hiện trong cây.

Ví dụ

Input

9
6 2 8 0 4 7 9 3 5
2 8

Output

6

Giải thích

Nút mang khóa $2$ nằm trong cây con trái của gốc $6$, còn nút mang khóa $8$ nằm trong cây con phải. Vì vậy không có nút nào nằm thấp hơn $6$ mà vẫn chứa cả hai nút trong cây con của nó.

Do đó LCA của $2$ và $8$ có khóa $6$.