AT_abc480_g [ABC480G] Zonal Score Minimization

The score of a sequence of positive integers of length at least $ 2 $ is defined as the difference between the maximum and minimum values of the sequence. You are given a sequence $ A $ of $ N $ positive integers. Find the minimum possible total score of the contiguous subsequences when $ A $ is divided into one or more contiguous subsequences, each of length at least $ 2 $ . More formally, find the minimum possible value of $ \sum_{k=1}^{K}\left(\max(B_k)-\min(B_k)\right) $ over all positive integers $ K $ and sequences of positive integers $ B_1,B_2,\dots,B_K $ , each of length at least $ 2 $ , such that concatenating $ B_1,B_2,\dots,B_K $ in this order yields $ A $ .

The input is given from Standard Input in the following format: > $ N $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

Print the answer in a single line.

### Sample Explanation 1 If $ A $ is divided into $ (1,3) $ and $ (6,8,9) $ , their scores are $ 2 $ and $ 3 $ , respectively, for a total of $ 5 $ . It is impossible to make the total score of the contiguous subsequences $ 4 $ or less, so the answer is $ 5 $ . ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq 10^9 $ - All input values are integers.