Apteka

Jaś는 약국 앞에 늘어선 줄의 맨 뒤에 서 있습니다. 몹시 급한 Jaś는 돈을 조금 내더라도 앞사람들과 자리를 바꿔서 앞으로 가려고 합니다.

모든 사람은 자리를 바꿔 줄 의향이 있지만, $i$번째 사람은 줄에서 한 칸 뒤로 물러날 때마다 $c_i$를 받아야 합니다. 정확히 말하면, Jaś가 어떤 사람보다 계산대에서 $k$칸($k > 0$) 더 멀리 떨어져 있고 그 사람과 자리를 바꾸고 싶다면, 그 사람에게 $k \cdot c_i$를 지불해야 합니다.

Jaś는 줄의 맨 앞에 서고 싶습니다. 지출을 최소로 하려면 어떻게 자리를 바꿔야 하는지 구하세요.

첫째 줄에 정수 $n$ ($1 \le n \le 10^6$)이 주어집니다. 이는 약국 줄에서 Jaś 앞에 서 있는 사람의 수입니다.

둘째 줄에 $n$개의 정수 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^9$)이 주어집니다. $c_i$는 Jaś가 $i$번째 사람을 한 칸 뒤로 보내기 위해 지불해야 하는 금액입니다. 사람의 번호는 Jaś가 바로 뒤에 서 있는 사람부터, 즉 줄의 맨 뒤에서 맨 앞 방향으로 매깁니다.

Jaś가 줄의 맨 앞에 서기 위해 지불해야 하는 최소 금액을 정수 하나로 출력합니다.

예시에서 Jaś는 먼저 앞에서 세 번째 사람과 $2 \cdot 2$의 비용으로 자리를 바꾸고, 그다음 맨 앞 사람과 $3 \cdot 2$의 비용으로 자리를 바꿉니다. 따라서 총 비용은 $10$입니다.