using System; using System.IO; using System.Collections.Generic; using System.Globalization; using System.Linq; using System.Text; using E = System.Linq.Enumerable; partial class Solver { public void Run() { var N = ni(); var Y = ni(N); long ans = 0; Array.Sort(Y); var dp = new long[N]; for (int i = 0; i < N; i++) { var v = long.MaxValue >> 10; if (i - 1 >= 0) { v = Math.Min(v, (i - 2 >= 0 ? dp[i - 2] : 0) + (Y[i] - Y[i - 1])); } if (i - 2 >= 0) { v = Math.Min(v, (i - 3 >= 0 ? dp[i - 3] : 0) + (Y[i] - Y[i - 2])); } dp[i] = v; } cout.WriteLine(dp[N - 1]); } } public class SumTable { private readonly long[] sumArray; public SumTable(long[] array) { sumArray = new long[array.Length + 1]; Array.Copy(array, 0, sumArray, 1, array.Length); for (int i = 1; i < sumArray.Length; i++) { sumArray[i] += sumArray[i - 1]; } } public long Sum(int begin, int end) { if (begin >= end) return 0; return sumArray[end] - sumArray[begin]; } } public class ModMatrix { public int Row { get; private set; } public int Col { get; private set; } public int Mod { get; private set; } private long[] Data; public ModMatrix(int row, int col, int mod) { this.Row = row; this.Col = col; this.Data = new long[Row * Col]; this.Mod = mod; } public ModMatrix(long[,] array, int mod) : this(array.GetLength(0), array.GetLength(1), mod) { int index = 0; for (int i = 0; i < Row; i++) { for (int j = 0; j < Col; j++) { Data[index++] = array[i, j] % mod; } } } public long this[int row, int col] { set { Data[row * Col + col] = value; } get { return Data[row * Col + col]; } } static public ModMatrix UnitMatrix(int n, int mod) { var matrix = new ModMatrix(n, n, mod); for (int i = 0; i < n; i++) { matrix[i, i] = 1; } return matrix; } static public ModMatrix operator +(ModMatrix A, ModMatrix B) { if (A.Mod != B.Mod) throw new InvalidOperationException("A.Mod must be equal to B.Mod"); var C = new ModMatrix(A.Row, A.Col, A.Mod); for (int i = 0; i < C.Data.Length; i++) { C.Data[i] = (A.Data[i] + B.Data[i] + A.Mod) % A.Mod; } return C; } static public ModMatrix operator -(ModMatrix A, ModMatrix B) { if (A.Mod != B.Mod) throw new InvalidOperationException("A.Mod must be equal to B.Mod"); var C = new ModMatrix(A.Row, A.Col, A.Mod); for (int i = 0; i < C.Data.Length; i++) { C.Data[i] = (A.Data[i] - B.Data[i] + A.Mod) % A.Mod; } return C; } static public ModMatrix operator *(ModMatrix A, ModMatrix B) { if (A.Mod != B.Mod) throw new InvalidOperationException("A.Mod must be equal to B.Mod"); var C = new ModMatrix(A.Row, B.Col, A.Mod); for (int i = 0; i < A.Row; i++) { for (int j = 0; j < B.Col; j++) { var val = C[i, j]; for (int k = 0; k < A.Col; k++) val = (val + A[i, k] * B[k, j]) % A.Mod; if (val < 0) val += A.Mod; C[i, j] = val; } } return C; } static public ModMatrix Pow(ModMatrix A, long n) { if (n == 0) return UnitMatrix(A.Row, A.Mod); if (n == 1) return A; ModMatrix result = A.Clone(), t = A.Clone(); n--; for (; n > 0; n >>= 1) { if ((n & 1) != 0) result = result * t; t = t * t; } return result; } public ModMatrix Clone() { return new ModMatrix(Row, Col, Mod) { Data = Data.Clone() as long[] }; } } // PREWRITEN CODE BEGINS FROM HERE partial class Solver : Scanner { public static void Main(string[] args) { #if LOCAL new Solver(Console.In, Console.Out).Run(); #else Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }); new Solver(Console.In, Console.Out).Run(); Console.Out.Flush(); #endif } #pragma warning disable IDE0052 private readonly TextReader cin; private readonly TextWriter cout; #pragma warning restore IDE0052 public Solver(TextReader reader, TextWriter writer) : base(reader) { this.cin = reader; this.cout = writer; } public Solver(string input, TextWriter writer) : this(new StringReader(input), writer) { } #pragma warning disable IDE1006 #pragma warning disable IDE0051 private int ni() { return NextInt(); } private int[] ni(int n) { return NextIntArray(n); } private long nl() { return NextLong(); } private long[] nl(int n) { return NextLongArray(n); } private double nd() { return NextDouble(); } private double[] nd(int n) { return NextDoubleArray(n); } private string ns() { return Next(); } private string[] ns(int n) { return NextArray(n); } #pragma warning restore IDE1006 #pragma warning restore IDE0051 } public static class LinqPadExtension { static public T Dump(this T obj) { #if LOCAL return LINQPad.Extensions.Dump(obj); #else return obj; #endif } } public class Scanner { private readonly TextReader Reader; private readonly Queue TokenQueue = new Queue(); private readonly CultureInfo ci = CultureInfo.InvariantCulture; public Scanner() : this(Console.In) { } public Scanner(TextReader reader) { this.Reader = reader; } public int NextInt() { return int.Parse(Next(), ci); } public long NextLong() { return long.Parse(Next(), ci); } public double NextDouble() { return double.Parse(Next(), ci); } public string[] NextArray(int size) { var array = new string[size]; for (int i = 0; i < size; i++) array[i] = Next(); return array; } public int[] NextIntArray(int size) { var array = new int[size]; for (int i = 0; i < size; i++) array[i] = NextInt(); return array; } public long[] NextLongArray(int size) { var array = new long[size]; for (int i = 0; i < size; i++) array[i] = NextLong(); return array; } public double[] NextDoubleArray(int size) { var array = new double[size]; for (int i = 0; i < size; i++) array[i] = NextDouble(); return array; } public string Next() { if (TokenQueue.Count == 0) { if (!StockTokens()) throw new InvalidOperationException(); } return TokenQueue.Dequeue(); } public bool HasNext() { if (TokenQueue.Count > 0) return true; return StockTokens(); } static readonly char[] _separator = new[] { ' ' }; private bool StockTokens() { while (true) { var line = Reader.ReadLine(); if (line == null) return false; var tokens = line.Split(_separator, StringSplitOptions.RemoveEmptyEntries); if (tokens.Length == 0) continue; foreach (var token in tokens) TokenQueue.Enqueue(token); return true; } } }