题目描述

译自 ROIR 2020 Day2 T1. Максимальное произведение

给定一个自然数组成的数组 $[a_1,a_2,\ldots,a_n]$。
定义一个数组的权值为这个数组中所有数的和。

请把这个数组划分为两个非空数组 $[a_1,a_2,\ldots,a_i]$ 和 $[a_{i+1},a_{i+2},\ldots,a_n]$，使得它们的权值之积尽量大。
你需要确定能够使得两个数组权值之积最大的 $i$。

输入格式

第一行，一个整数 $n$，表示元素的个数。
第二行，$n$ 个整数 $a_1,a_2,\ldots,a_n$，表示数组中的元素。

输出格式

输出能使得 $[a_1,a_2,\ldots,a_i]$ 和 $[a_{i+1},a_{i+2},\ldots,a_n]$ 权值之积最大的 $i$。
若有多解，随意输出一解即可。

样例

3
1 2 3

2

如果你选择 $i=1$，则权值之积为 $1 \cdot (2+3) = 5$。 如果你选择 $i=2$，则权值之积为 $(1+2) \cdot 3 = 9$。

数据范围与提示

对于 $100\%$ 的数据，$2 \le n \le 2\cdot 10^5, 1 \le a_i \le 10^9$。
具体数据限制如下表：