A toll network is stored as a binary search tree keyed by distinct integer gate ids. Starting from an empty tree, the ids are inserted one at a time in the order given (standard BST insertion: go left when the new id is smaller than the current node, otherwise go right); this determines the tree's shape. Given two distinct gate ids u and v, both guaranteed to be present, report the sum of the ids on every node along the unique tree path connecting u and v, including both endpoints.
Input format
Line 1: an integer n, the number of gates.
Line 2: n space-separated distinct integers, the gate ids in insertion order.
Line 3: two space-separated distinct integers u and v, both present in the tree.
Output format
A single integer: the sum of the gate ids on the path between u and v (inclusive of both).
Constraints
- 2 <= n <= 40
- All gate ids are distinct, each with absolute value <= 1000000.
uandvare distinct and both appear among the ids.