Highways

In a distant country named Lineland there are $N$ cities, all lying along a single highway on a straight line. The highway starts at city 1, runs through city 2, city 3, and so on, and ends at city $N$. City $i$ is located $X_i$ miles from city 1 (so $X_1 = 0$, and the cities are ordered from left to right by number).

The highway is wide and smooth and a pleasure to drive, but every road in Lineland is one-way. People may drive along the highway only from a lower-numbered city toward a higher-numbered one; to get back they must use country roads, which is far less pleasant.

The new president wants to make travelling between cities easier, but he will not break tradition by making the highway two-way. Instead he will build new one-way highways so that, using only highways, one can get from any city to any other city (that is, so that the directed road network becomes strongly connected).

The president will build exactly two new highways. Each highway is a one-way road connecting two different cities. A new highway must not pass through any city other than the two it connects, and the four cities that serve as endpoints of the two highways must all be distinct.

You must choose which cities the two new highways connect. Since the cost of a highway is proportional to its length, the total length of the two highways must be as small as possible. Assume the length of a new highway between two cities equals the distance between those cities along the main highway.

The first line contains the integer $N$ ($2 \le N \le 50\,000$).

The second line contains $N-1$ integers $X_2, X_3, \ldots, X_N$ separated by spaces ($1 \le X_2 < X_3 < \cdots < X_N \le 10^9$). City 1 is always at position $X_1 = 0$.

If it is impossible to build the two highways satisfying all requirements, print $0$.

Otherwise, print a single integer: the minimal possible total length of the two highways to be built.