Tổng giá trị trong đoạn của BST (Range Sum of BST)

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 số nguyên low và high với $\text{low}\le\text{high}$. Hãy tính tổng khóa của tất cả các nút có giá trị nằm trong đoạn đóng $[\text{low},\text{high}]$.

Mỗi nút được tính đúng một lần.

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 số nguyên low high.

Output

In một số nguyên là tổng khóa của các nút có giá trị thuộc đoạn $[\text{low},\text{high}]$.

Subtask

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

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

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

Trong tất cả các subtask, $1\le a_i\le 10^5$, $1\le\text{low}\le\text{high}\le 10^5$ và các $a_i$ phân biệt.

Ví dụ

Input

7
10 5 15 3 7 18 13
7 15

Output

45

Giải thích

Các khóa của cây lần lượt gồm $10,5,15,3,7,18,13$. Với đoạn đóng $[7,15]$, các khóa $7$, $10$, $13$ và $15$ nằm trong đoạn; các khóa $3$, $5$ nhỏ hơn $7$, còn $18$ lớn hơn $15$ nên không được tính.

Tổng cần tìm là $7+10+13+15=45$, vì vậy chương trình in 45.