题目描述

给定一个自然数组成的数组 $[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

说明/提示

【样例 1 解释】

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

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

【数据范围】

对于 100% 的数据，$2 \leq n \leq 10^5$, $1 \leq a_i \leq 10^4$。