Range Sum of BST

Source: LeetCode

Version: Phuoc Hung OJ Extended

Problem Statement

Build a BST from the $n$ distinct keys $a_1,a_2,\ldots,a_n$ in insertion order.

Given integers low and high with $\text{low}\le\text{high}$, compute the sum of the keys of all nodes whose values lie in the closed interval $[\text{low},\text{high}]$.

Each node contributes exactly once.

Input

The first line contains $n$.

The second line contains the $n$ distinct keys $a_1,a_2,\ldots,a_n$.

The third line contains low high.

Output

Print one integer: the sum of all node keys in $[\text{low},\text{high}]$.

Subtasks

Subtask 1 (20 points): $1\le n\le 20$.

Subtask 2 (30 points): $1\le n\le 500$.

Subtask 3 (50 points): $1\le n\le 2\cdot 10^4$.

In all subtasks, $1\le a_i\le 10^5$, $1\le\text{low}\le\text{high}\le 10^5$, and all $a_i$ are distinct.

Examples

Input

7
10 5 15 3 7 18 13
7 15

Output

45

Explanation

The tree contains keys $10,5,15,3,7,18,13$. For the closed interval $[7,15]$, keys $7$, $10$, $13$, and $15$ are included; keys $3$ and $5$ are below the interval, while $18$ is above it.

Therefore the required sum is $7+10+13+15=45$, so the program prints 45.