package main

import (
	"bufio"
	"fmt"
	"math"
	"math/bits"
	"os"
	"sort"
)

type Line struct {
	m  int64
	b  int64
	id int
}

func abs(x int64) int64 {
	if x < 0 {
		return -x
	}
	return x
}

func bad(L1, L2, L3 Line) bool {
	dy32 := L3.b - L2.b
	dx12 := L1.m - L2.m
	dy21 := L2.b - L1.b
	dx23 := L2.m - L3.m

	hi1, lo1 := bits.Mul64(uint64(abs(dy32)), uint64(abs(dx12)))
	hi2, lo2 := bits.Mul64(uint64(abs(dy21)), uint64(abs(dx23)))

	sign1 := 1
	if dy32 < 0 {
		sign1 = -sign1
	}

	sign2 := 1
	if dy21 < 0 {
		sign2 = -sign2
	}

	if sign1 != sign2 {
		return sign1 < sign2
	}

	if sign1 == 1 {
		if hi1 != hi2 {
			return hi1 < hi2
		}
		return lo1 <= lo2
	} else {
		if hi1 != hi2 {
			return hi1 > hi2
		}
		return lo1 >= lo2
	}
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	fmt.Fscan(reader, &n)

	c := make([]int64, n+1)
	for i := 1; i <= n; i++ {
		fmt.Fscan(reader, &c[i])
	}

	initialS := make([]int64, n+2)
	for i := n; i >= 1; i-- {
		initialS[i] = initialS[i+1] + c[i]
	}

	B := 300
	numBlocks := (n + B - 1) / B

	blockStart := make([]int, numBlocks)
	blockEnd := make([]int, numBlocks)
	sortedIndices := make([][]int, numBlocks)

	for k := 0; k < numBlocks; k++ {
		blockStart[k] = k*B + 1
		blockEnd[k] = (k + 1) * B
		if blockEnd[k] > n {
			blockEnd[k] = n
		}
		for i := blockStart[k]; i <= blockEnd[k]; i++ {
			sortedIndices[k] = append(sortedIndices[k], i)
		}
		sort.Slice(sortedIndices[k], func(x, y int) bool {
			return c[sortedIndices[k][x]] < c[sortedIndices[k][y]]
		})
	}

	removed := make([]bool, n+1)
	remBlockCount := make([]int, numBlocks)
	sumRemBlock := make([]int64, numBlocks)
	deltaR := make([]int, numBlocks)
	deltaS := make([]int64, numBlocks)

	r := make([]int64, n+1)
	s := make([]int64, n+1)
	b_val := make([]int64, n+1)

	hull := make([][]Line, numBlocks)
	ptr := make([]int, numBlocks)

	rebuild := func(k int) {
		curr_r := int64(0)
		curr_s := sumRemBlock[k]

		for i := blockStart[k]; i <= blockEnd[k]; i++ {
			if removed[i] {
				curr_r++
				curr_s -= c[i]
			} else {
				r[i] = curr_r
				s[i] = curr_s
				b_val[i] = int64(i)*c[i] + initialS[i+1] - r[i]*c[i] - s[i]
			}
		}

		hull[k] = hull[k][:0]
		for _, i := range sortedIndices[k] {
			if removed[i] {
				continue
			}
			L := Line{m: -c[i], b: b_val[i], id: i}
			for len(hull[k]) > 0 && hull[k][len(hull[k])-1].m == L.m {
				if L.b >= hull[k][len(hull[k])-1].b {
					goto skip
				} else {
					hull[k] = hull[k][:len(hull[k])-1]
				}
			}
			for len(hull[k]) >= 2 && bad(hull[k][len(hull[k])-2], hull[k][len(hull[k])-1], L) {
				hull[k] = hull[k][:len(hull[k])-1]
			}
			hull[k] = append(hull[k], L)
		skip:
		}
		ptr[k] = 0
		if len(hull[k]) > 0 {
			X := int64(deltaR[k])
			for ptr[k] < len(hull[k])-1 {
				val1 := hull[k][ptr[k]].m*X + hull[k][ptr[k]].b
				val2 := hull[k][ptr[k]+1].m*X + hull[k][ptr[k]+1].b
				if val2 <= val1 {
					ptr[k]++
				} else {
					break
				}
			}
		}
	}

	getMin := func(k int) (int64, int) {
		if len(hull[k]) == 0 {
			return math.MaxInt64, -1
		}
		X := int64(deltaR[k])
		for ptr[k] < len(hull[k])-1 {
			val1 := hull[k][ptr[k]].m*X + hull[k][ptr[k]].b
			val2 := hull[k][ptr[k]+1].m*X + hull[k][ptr[k]+1].b
			if val2 <= val1 {
				ptr[k]++
			} else {
				break
			}
		}
		best := hull[k][ptr[k]]
		return best.m*X + best.b - deltaS[k], best.id
	}

	for k := 0; k < numBlocks; k++ {
		rebuild(k)
	}

	for {
		minVal := int64(math.MaxInt64)
		bestId := -1
		bestBlock := -1

		for k := 0; k < numBlocks; k++ {
			val, id := getMin(k)
			if id != -1 && val < minVal {
				minVal = val
				bestId = id
				bestBlock = k
			}
		}

		if minVal >= 0 || bestId == -1 {
			break
		}

		removed[bestId] = true
		remBlockCount[bestBlock]++
		sumRemBlock[bestBlock] += c[bestId]

		for k := bestBlock + 1; k < numBlocks; k++ {
			deltaR[k]++
		}
		for k := 0; k < bestBlock; k++ {
			deltaS[k] += c[bestId]
		}

		rebuild(bestBlock)
	}

	ans := int64(0)
	idx := int64(1)
	for i := 1; i <= n; i++ {
		if !removed[i] {
			ans += idx * c[i]
			idx++
		}
	}
	fmt.Println(ans)
}