003 - Product Maximization

問題

長さ $N$ の整数からなる数列 $A = (a_1,a_2,\ldots,a_N)$ が与えられます。

$A$ から $k$ $(1 \leq k \leq N)$ 番目の要素を取り除いた数列を $B = (b_1,b_2,\ldots,b_{N-1})$ とします。
$\displaystyle \prod_{i=1}^{N-1} b_i$ が最大となる正整数 $k$ を求めてください。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$a_1$ $a_2$ $\ldots$ $a_N$

出力

$\displaystyle \prod_{i=1}^{N-1} b_i$ が最大となる正整数 $k$ を出力せよ。
出力の末尾には改行を入れること。

制約

• $2 \leq N \leq 10^5$
• $-10^9 \leq a_i \leq 10^9$ $(1 \leq i \leq N)$
• $a_i \neq 0$
• $A$ の要素は全て相異なる
• 入力は全て整数

入出力例

入力例１

5
2 4 1 3 5

出力例１

3

$k=3$ とすることで $2 \times 4 \times 3 \times 5 = 120$ となり、これが最大となります。

入力例２

5
-3 2 4 -5 -1

出力例２

5

$k = 5$ とすることで $-3 \times 2 \times 4 \times -5 = 120$ となり、これが最大となります。