고속도로

Lineland라는 나라에 $N$개의 도시가 하나의 고속도로를 따라 일직선으로 늘어서 있다. 고속도로는 직선이며, 1번 도시에서 시작해 2번, 3번 도시를 차례로 지나 $N$번 도시에서 끝난다. $i$번 도시는 1번 도시로부터 $X_i$마일 떨어진 지점에 있다(따라서 $X_1 = 0$이고, 도시들은 번호 순서대로 왼쪽에서 오른쪽으로 놓여 있다).

고속도로는 넓고 잘 닦여 있어 달리기 좋지만, Lineland의 모든 도로는 일방통행이다. 그래서 사람들은 번호가 작은 도시에서 큰 도시 쪽으로만 고속도로를 달릴 수 있으며, 되돌아가려면 국도를 이용해야 한다.

새 대통령은 도시 사이를 오가기 더 편하게 만들고 싶지만, 고속도로를 양방향으로 바꾸는 전통 파괴는 원치 않는다. 그래서 새로운 일방통행 고속도로를 지어서, 어떤 도시에서 출발하든 고속도로만으로 다른 모든 도시에 도달할 수 있게 하려고 한다(즉, 도로의 방향 그래프가 강하게 연결되도록).

대통령은 정확히 두 개의 새 고속도로를 짓기로 했다. 각 고속도로는 서로 다른 두 도시를 잇는 일방통행 도로이다. 새 고속도로는 잇는 두 도시 외의 다른 도시를 지나지 않아야 하며, 두 고속도로의 끝점이 되는 네 도시는 모두 서로 달라야 한다.

당신은 이 두 고속도로가 이을 도시를 정해야 한다. 건설 비용은 길이에 비례하므로, 두 고속도로의 길이 합이 최소가 되도록 하라. 두 도시를 잇는 새 고속도로의 길이는 그 두 도시 사이의 고속도로 상 거리와 같다고 가정한다.

첫째 줄에 정수 $N$이 주어진다 ($2 \le N \le 50\,000$).

둘째 줄에 $N-1$개의 정수 $X_2, X_3, \ldots, X_N$이 공백으로 구분되어 주어진다 ($1 \le X_2 < X_3 < \cdots < X_N \le 10^9$). 1번 도시의 위치는 항상 $X_1 = 0$이다.

조건을 모두 만족하도록 두 고속도로를 건설하는 것이 불가능하면 $0$을 출력한다.

가능하다면, 건설해야 하는 두 고속도로의 최소 가능한 길이 합을 정수 하나로 출력한다.