题目内容

小图有一排共 $n$ 本书，编号依次为 $1$ 到 $n$，第 $i$ 本书的热度指数为 $a_i$。他打算将这排书分成前后两个连续的展示区，第一个区包含前 $k$（$1 \le k \le n-1$）本书，第二个区包含其余书。定义这种划分的代价为第一个区所有书热度指数之和与第二个区所有书热度指数之和的乘积。小图希望找出所有可能划分中的最小代价。

书的本数 $n$ 满足 $2 \le n \le 10^6$，每本书的热度指数 $a_i$ 满足 $-10^3 \le a_i \le 10^3$。

输入描述

第一行包含一个整数 $n$，表示书的本数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，依次表示每本书的热度指数，相邻整数之间用空格分隔。