물리를 잘하는 시시포스는 오늘도 우울

고대 그리스의 시시포스는 영원히 돌을 굴려야 하는 형벌을 받게 되었다. 시시포스가 돌을 굴리는 땅은 일직선으로 놓여 있으며, $1$부터 $N$까지 번호가 붙은 $N$개의 평지와 서로 인접한 평지를 잇는 $N-1$개의 비탈길로 이루어져 있다. 각 평지의 높이는 $A_1, A_2, \cdots, A_N$이다. 평지의 높이는 정수이며, 임의의 $2 \leq i \leq N$에 대하여 다음 두 조건 중 하나를 만족한다:

1. $A_{i-1} < A_i > A_{i+1}$
2. $A_{i-1} > A_i < A_{i+1}$

시시포스는 오랜 세월 돌을 굴리다, 마침내 역학적 에너지 보존의 법칙을 깨달았다! 이는 어떤 평지에서 돌을 굴려 내려가면, 다시 그 돌이 출발했던 높이와 동일한 높이까지는 힘들이지 않고도 굴러간다는 법칙이다. 시시포스는 역학적 에너지 보존 법칙을 이용하여 $A_i \geq A_j$이고 $i$번 평지와 $j$번 평지 사이에 $A_i$보다 높은 평지가 존재하지 않을 때, 힘을 들이지 않고 $i$번 평지에서 돌을 굴려 $j$번 평지로 이동시킬 수 있다.

또한, 시시포스는 돌을 인접한 두 평지 사이에서 이동시킬 수 있는 에스컬레이터를 설치할 수 있다. 높이가 $A_i$와 $A_{i+1}$인 두 평지 사이에 에스컬레이터를 설치하는 데 필요한 비용은 $|A_i - A_{i+1}|$이다. 에스컬레이터가 설치되면, 힘을 들이지 않고 돌을 $i$번 평지에서 $i+1$번 평지로 또는 $i+1$번 평지에서 $i$번 평지로 자유롭게 이동시킬 수 있다. 에스컬레이터는 서로 인접한 두 평지 사이의 비탈길에만 설치할 수 있으며, 두 평지를 완전히 이어야 한다. 예를 들어, 높이 $1$과 $3$인 두 평지가 서로 인접해 있을 때, 높이 $1$에서 $2$까지만 에스컬레이터를 잇는 것은 불가능하다. 또한 시시포스가 에스컬레이터를 이용할 경우, 도착한 평지에서 즉시 멈춘다.

시시포스는 에스컬레이터가 설치되어 있는 비탈길을 지날 때, 에스컬레이터를 타지 않고 역학적 보존 법칙을 이용하여 공을 굴려 지나갈 수 있지만, 역학적 에너지 법칙을 이용하여 공을 굴리는 도중에 에스컬레이터를 이용할 수는 없다.

시시포스는 역학적 에너지 보존의 법칙과 에스컬레이터를 사용하여 어떤 평지에서 출발하여도 다른 모든 평지에 도달할 수 있도록 에스컬레이터를 설치하고 싶다. 물리는 잘하지만 계산에는 약한 시시포스를 위해, 시시포스가 힘들이지 않고 임의의 평지에서 임의의 다른 모든 평지로 돌을 옮길 수 있도록 에스컬레이터를 설치하는 데 필요한 최소 총 비용을 구해 보자.

첫째 줄에 평지의 개수 $N$이 주어진다. $(3 \leq N \leq 10^6)$

둘째 줄에 평지의 높이를 나타내는 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. $(-10^9 \leq A_i \leq 10^9)$

시시포스가 에스컬레이터를 설치하는 데 필요한 최소 총 비용을 출력한다.