Maximizing Gem Trade Profit in a Tree-Like World

ZJY is planning a trip to a new world where the cities are arranged in a tree structure. In this world, each city holds a unique gem with an initial price. The tree property guarantees that for any two cities there is exactly one path connecting them.

ZJY’s plan is to buy a gem in one city (city A) and later sell it in another city (city B). However, whenever ZJY passes through a city (including the selling city B, but excluding the buying city A), its gem price increases. The rule is that when she passes a city, that city’s gem price increases by an amount equal to its original price. Therefore, if the gem price in city B is v initially, by the time ZJY sells there, its price becomes v + v = 2v (note that if A and B are the same city then no travel occurs; in our problem A and B must be distinct, so if A’s price is v, selling there would still yield a price of v and no profit is made).

Thus, if ZJY buys in city A at price \( p_A \) and sells in city B at a boosted price \( 2p_B \), her profit is calculated as:

\( \text{Profit} = 2p_B - p_A \)

Your task is to determine the maximum profit ZJY can obtain by choosing an appropriate pair of distinct cities A and B.

inputFormat

The input consists of two lines:

1. The first line contains a single integer \( n \) (\( n \ge 2 \)), representing the number of cities.
2. The second line contains \( n \) space-separated integers, where the \( i\text{-th} \) integer denotes the initial gem price \( p_i \) in the \( i\text{-th} \) city.

You may assume that all prices are positive integers.

outputFormat

Output a single integer denoting the maximum profit ZJY can achieve.

sample

3
3 6 1

11