using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using System.Threading.Tasks;
using System.Globalization;
namespace Atcoder
{
    class Program
    {
        public static long[] kaij;
        static void Main(string[] args)
        {
            StreamScanner scan = new StreamScanner(System.Console.OpenStandardInput());
            int n = scan.Integer();
             a = scan.Long(n);
            s = new long[n + 1];
            for (int i = 0; i < n; i++)
            {
                s[i + 1] = a[i] + s[i];
            }
            dp = new long[n, n];
            long res = solve(0, n - 1);
            Console.WriteLine(res);
        }
        static long[,] dp;
        static long[] a;
        static long[] s;
        public static long solve(int migi,int hidari)
        {
            if (migi == hidari) { return 0; }
            if (dp[migi, hidari] > 0) { return dp[migi, hidari]; }
            long min = long.MaxValue;
            for (int i = migi; i < hidari; i++)
            {
                min = Math.Min(min, solve(migi, i) + solve(i + 1, hidari));
            }
            dp[migi, hidari] = min + s[hidari + 1] - s[migi];
            return dp[migi, hidari];
        }
        public static long kaijyo(int n)
        {
            if (n <= 1)
                return 1;
            if (kaij[n] > 0)
                return kaij[n];
            long kekka = n * kaijyo(n - 1);
            return kekka;
        }

        public static long modPow(long a,long n,long p)//a^n(mod p)
        {
            if (n == 1) { return a % p; }
            if (n % 2 == 1) { return (a * modPow(a, n - 1, p)) % p; }
            long buf = modPow(a, n / 2, p);
            return (buf * buf) % p;
        }
        
    }
    public class Mlong
    {
        private static long mod = 1000000007;
        public long num;
        public Mlong(long num) { this.num = num; }
        public override int GetHashCode()
        {
            return num.GetHashCode();
        }
        public override bool Equals(object obj)
        {
            return num.Equals(obj);
        }
        public static Mlong operator +(Mlong x, Mlong y)
        {
            return new Mlong((x.num + y.num) % mod);
        }
        public static Mlong operator -(Mlong x, Mlong y)
        {
            return new Mlong((x.num - y.num + mod) % mod);
        }
        public static Mlong operator *(Mlong x, Mlong y)
        {
            return new Mlong((long)(((1L * x.num) * y.num) % mod));
        }
        public Mlong hutujyo(Mlong x)
        {
            return new Mlong(num / x.num);
        }
        public Mlong modjyo(Mlong x)
        {
            return num * x.Pow(mod - 2);
        }
        public static implicit operator Mlong(long x)
        {
            return new Mlong(x);
        }
        public static Mlong operator %(Mlong x, Mlong y)
        {
            return new Mlong(x.num % y.num);
        }
        public static bool operator ==(Mlong x, Mlong y)
        {
            return x.num == y.num;
        }
        public static bool operator !=(Mlong x, Mlong y)
        {
            return x.num != y.num;
        }
        public static bool operator <(Mlong x, Mlong y)
        {
            return x.num < y.num;
        }
        public static bool operator >(Mlong x, Mlong y)
        {
            return x.num > y.num;
        }
        public static bool operator <=(Mlong x, Mlong y)
        {
            return x.num <= y.num;
        }
        public static bool operator >=(Mlong x, Mlong y)
        {
            return x.num >= y.num;
        }
        public Mlong Pow(Mlong n)
        {

            if (n == 1) { return this % mod; }
            if (n % 2 == 1) { return (this * Pow(n - 1)) % mod; }
            Mlong buf = Pow(n.hutujyo(2));
            return (buf * buf) % mod;
        }
        public static Mlong Pow(Mlong a, Mlong n)
        {
            return a.Pow(n);
        }
        public static Mlong Comb(Mlong n, Mlong a)
        {
            Mlong buf1 = 1;
            Mlong buf2 = 1;
            for (long i = 0; i < a; i++)
            {
                buf1 *= n - i;
                buf2 *= (i + 1);
            }
            return buf1.modjyo(buf2);

        }
        public static void WriteLine(Mlong x)
        {
            Console.WriteLine(x.num);
          
        }
    }
    public class Mint
    {
        private static int mod = 1000000007;
        public int num;
        public Mint(int Num) { num = Num; }
        public override int GetHashCode()
        {
            return num.GetHashCode();
        }
        public override bool Equals(object obj)
        {
            return num.Equals(obj);
        }
        public static Mint operator +(Mint x, Mint y)
        {
            return new Mint((x.num + y.num) % mod);
        }
        public static Mint operator -(Mint x, Mint y)
        {
            return new Mint((x.num - y.num + mod) % mod);
        }
        public static Mint operator *(Mint x, Mint y)
        {
            return new Mint((int)(((1L * x.num) * y.num) % mod));
        }
        public Mint hutujyo(Mint x)
        {
            return new Mint(num / x.num);
        }
        public Mint modjyo(Mint x)
        {
            return num * x.Pow(mod - 2);
        }
        public static implicit operator Mint(int x)
        {
            return new Mint(x);
        }
        public static Mint[] Toarray(int[]x)
        {
            Mint[] buf = new Mint[x.Length];
            for (int i = 0; i < x.Length; i++)
            {
                buf[i] = x[i];
            }
            return buf;
        }
        public static explicit  operator int(Mint x)
        {
            return x.num;
        }
        public static Mint operator %(Mint x,Mint y)
        {
            return new Mint(x.num % y.num);
        }
        public static bool operator ==(Mint x, Mint y)
        {
            return x.num == y.num;
        }
        public static bool operator !=(Mint x, Mint y)
        {
            return x.num != y.num;
        }
        public static bool operator <(Mint x, Mint y)
        {
            return x.num < y.num;
        }
        public static bool operator >(Mint x, Mint y)
        {
            return x.num > y.num;
        }
        public static bool operator <=(Mint x, Mint y)
        {
            return x.num <= y.num;
        }
        public static bool operator >=(Mint x, Mint y)
        {
            return x.num >= y.num;
        }
        public Mint Pow(Mint n)
        {

            if (n == 1) { return this % mod; }
            if (n % 2 == 1) { return (this * Pow(n - 1)) % mod; }
            Mint buf = Pow(n.hutujyo(2));
            return (buf * buf) % mod;
        }
        public static Mint Pow(Mint a, Mint n)
        {
            return a.Pow(n);
        }
        public static Mint Comb(Mint n,Mint a)
        {
            Mint buf1 = 1;
            Mint buf2 = 1;
            for (int i = 0; i < a; i++)
            {
                buf1 *= n - i;
                buf2 *= (i + 1);
            }
            return buf1.modjyo(buf2);

        }
        public static void WriteLine(Mint x)
        {
            Console.WriteLine(x.num);

        }
    }
    public class StreamScanner
    {
        public StreamScanner(Stream stream) { str = stream; }
        private readonly Stream str;
        private readonly byte[] buf = new byte[1024];
        private int len, ptr;
        public bool isEof = false;
        public bool IsEndOfStream { get { return isEof; } }
        private byte read()
        {
            if (isEof) throw new EndOfStreamException();
            if (ptr >= len)
            {
                ptr = 0;
                if ((len = str.Read(buf, 0, 1024)) <= 0)
                {
                    isEof = true;
                    return 0;
                }
            }
            return buf[ptr++];
        }
        public char Char()
        {
            byte b = 0;
            do b = read();
            while (b < 33 || 126 < b);
            return (char)b;
        }
        public char[] Char(int n)
        {
            char[] kore = new char[n];
            for (int i = 0; i < n; i++)
            {
                kore[i] = Char();
            }
            return kore;
        }
        public string Scan()
        {
            var sb = new StringBuilder();
            for (var b = Char(); b >= 33 && b <= 126; b = (char)read())
                sb.Append(b);
            return sb.ToString();
        }
        public long Long()
        {
            long ret = 0; byte b = 0; var ng = false;
            do b = read();
            while (b != '-' && (b < '0' || '9' < b));
            if (b == '-') { ng = true; b = read(); }
            for (; true; b = read())
            {
                if (b < '0' || '9' < b)
                    return ng ? -ret : ret;
                else ret = ret * 10 + b - '0';
            }
        }
        public long[] Long(int n)
        {
            long[] kore = new long[n];
            for (int i = 0; i < n; i++)
            {
                kore[i] = Long();
            }
            return kore;
        }
        public int Integer() { return (int)Long(); }
        public int[] Integer(int n)
        {
            int[] kore = new int[n];
            for (int i = 0; i < n; i++)
            {
                kore[i] = (int)Long();
            }
            return kore;
        }
        public double Double() { return double.Parse(Scan(), CultureInfo.InvariantCulture); }
    }
    public class UnionFind
    {
        public int[] data;

        public UnionFind(int size)
        {
            data = new int[size];
            for (int i = 0; i < size; i++) data[i] = -1;
        }

        public bool Unite(int x, int y)
        {
            x = Root(x);
            y = Root(y);

            if (x != y)
            {
                if (data[y] < data[x])
                {
                    var tmp = y;
                    y = x;
                    x = tmp;
                }
                data[x] += data[y];
                data[y] = x;
            }
            return x != y;
        }

        public bool IsSameGroup(int x, int y)
        {
            return Root(x) == Root(y);
        }

        public int Root(int x)
        {
            return data[x] < 0 ? x : data[x] = Root(data[x]);
        }
    }
    public class SB_BinarySearchTree<T> where T : IComparable
    {
        public class Node
        {
            public T Value;
            public Node LChild;
            public Node RChild;
            public int Count;     //size of the sub tree

            public Node(T v)
            {
                Value = v;
                Count = 1;
            }
        }

        static Random _rnd = new Random();

        public static int Count(Node t)
        {
            return t == null ? 0 : t.Count;
        }

        static Node Update(Node t)
        {
            t.Count = Count(t.LChild) + Count(t.RChild) + 1;
            return t;
        }

        public static Node Merge(Node l, Node r)
        {
            if (l == null || r == null) return l == null ? r : l;

            if ((double)Count(l) / (double)(Count(l) + Count(r)) > _rnd.NextDouble())
            {
                l.RChild = Merge(l.RChild, r);
                return Update(l);
            }
            else
            {
                r.LChild = Merge(l, r.LChild);
                return Update(r);
            }
        }

        /// <summary>
        /// split as [0, k), [k, n)
        /// </summary>
        public static Tuple<Node, Node> Split(Node t, int k)
        {
            if (t == null) return new Tuple<Node, Node>(null, null);
            if (k <= Count(t.LChild))
            {
                var s = Split(t.LChild, k);
                t.LChild = s.Item2;
                return new Tuple<Node, Node>(s.Item1, Update(t));
            }
            else
            {
                var s = Split(t.RChild, k - Count(t.LChild) - 1);
                t.RChild = s.Item1;
                return new Tuple<Node, Node>(Update(t), s.Item2);
            }
        }

        public static Node Remove(Node t, T v)
        {
            if (Find(t, v) == null) return t;
            return RemoveAt(t, LowerBound(t, v));
        }

        public static Node RemoveAt(Node t, int k)
        {
            var s = Split(t, k);
            var s2 = Split(s.Item2, 1);
            return Merge(s.Item1, s2.Item2);
        }

        public static bool Contains(Node t, T v)
        {
            return Find(t, v) != null;
        }

        public static Node Find(Node t, T v)
        {
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);
                if (cmp > 0) t = t.LChild;
                else if (cmp < 0) t = t.RChild;
                else break;
            }
            return t;
        }

        public static Node FindByIndex(Node t, int idx)
        {
            if (t == null) return null;

            var currentIdx = Count(t) - Count(t.RChild) - 1;
            while (t != null)
            {
                if (currentIdx == idx) return t;
                if (currentIdx > idx)
                {
                    t = t.LChild;
                    currentIdx -= (Count(t == null ? null : t.RChild) + 1);
                }
                else
                {
                    t = t.RChild;
                    currentIdx += (Count(t == null ? null : t.LChild) + 1);
                }
            }

            return null;
        }

        public static int UpperBound(Node t, T v)
        {
            var torg = t;
            if (t == null) return -1;

            var ret = Int32.MaxValue;
            var idx = Count(t) - Count(t.RChild) - 1;
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);

                if (cmp > 0)
                {
                    ret = Math.Min(ret, idx);
                    t = t.LChild;
                    idx -= (Count(t == null ? null : t.RChild) + 1);
                }
                else if (cmp <= 0)
                {
                    t = t.RChild;
                    idx += (Count(t == null ? null : t.LChild) + 1);
                }
            }
            return ret == Int32.MaxValue ? Count(torg) : ret;
        }

        public static int LowerBound(Node t, T v)
        {
            var torg = t;
            if (t == null) return -1;

            var idx = Count(t) - Count(t.RChild) - 1;
            var ret = Int32.MaxValue;
            while (t != null)
            {
                var cmp = t.Value.CompareTo(v);
                if (cmp >= 0)
                {
                    if (cmp == 0) ret = Math.Min(ret, idx);
                    t = t.LChild;
                    if (t == null) ret = Math.Min(ret, idx);
                    idx -= t == null ? 0 : (Count(t.RChild) + 1);
                }
                else if (cmp < 0)
                {
                    t = t.RChild;
                    idx += (Count(t == null ? null : t.LChild) + 1);
                    if (t == null) return idx;
                }
            }
            return ret == Int32.MaxValue ? Count(torg) : ret;
        }

        public static Node Insert(Node t, T v)
        {
            var ub = LowerBound(t, v);
            return InsertByIdx(t, ub, v);
        }

        static Node InsertByIdx(Node t, int k, T v)
        {
            var s = Split(t, k);
            return Merge(Merge(s.Item1, new Node(v)), s.Item2);
        }

        public static IEnumerable<T> Enumerate(Node t)
        {
            var ret = new List<T>();
            Enumerate(t, ret);
            return ret;
        }

        static void Enumerate(Node t, List<T> ret)
        {
            if (t == null) return;
            Enumerate(t.LChild, ret);
            ret.Add(t.Value);
            Enumerate(t.RChild, ret);
        }
    }
    public class Set<T> where T : IComparable
    {
        protected SB_BinarySearchTree<T>.Node _root;

        public T this[int idx] { get { return ElementAt(idx); } }

        public int Count()
        {
            return SB_BinarySearchTree<T>.Count(_root);
        }

        public virtual void Insert(T v)
        {
            if (_root == null) _root = new SB_BinarySearchTree<T>.Node(v);
            else
            {
                if (SB_BinarySearchTree<T>.Find(_root, v) != null) return;
                _root = SB_BinarySearchTree<T>.Insert(_root, v);
            }
        }

        public void Clear()
        {
            _root = null;
        }

        public void Remove(T v)
        {
            _root = SB_BinarySearchTree<T>.Remove(_root, v);
        }

        public bool Contains(T v)
        {
            return SB_BinarySearchTree<T>.Contains(_root, v);
        }

        public T ElementAt(int k)
        {
            var node = SB_BinarySearchTree<T>.FindByIndex(_root, k);
            if (node == null) throw new IndexOutOfRangeException();
            return node.Value;
        }

        public int Count(T v)
        {
            return SB_BinarySearchTree<T>.UpperBound(_root, v) - SB_BinarySearchTree<T>.LowerBound(_root, v);
        }

        public int LowerBound(T v)
        {
            return SB_BinarySearchTree<T>.LowerBound(_root, v);
        }

        public int UpperBound(T v)
        {
            return SB_BinarySearchTree<T>.UpperBound(_root, v);
        }

        public Tuple<int, int> EqualRange(T v)
        {
            if (!Contains(v)) return new Tuple<int, int>(-1, -1);
            return new Tuple<int, int>(SB_BinarySearchTree<T>.LowerBound(_root, v), SB_BinarySearchTree<T>.UpperBound(_root, v) - 1);
        }

        public List<T> ToList()
        {
            return new List<T>(SB_BinarySearchTree<T>.Enumerate(_root));
        }
    }
}

Measured memory_bytes: 13140