Description

Given an integer sequence $A$ with $n$ elements, denoted as $A_1, A_2, A_3, \ldots, A_n$.

Find another integer sequence $X$ with $n$ elements. Let $S=\sum\limits_{i=1}^nA_i\times X_i$, such that $S>0$ and $S$ is as small as possible.

Input Format

The first line contains an integer $n$, the number of elements in the sequence.

The second line contains $n$ integers, the sequence $A$.

Output Format

Output a single integer on one line, the minimal value of $S$ subject to $S>0$.

2
4059 -1782

99

Hint

Constraints: For $100\%$ of the testdata, $1 \le n \le 20$, $|A_i| \le 10^5$, and the sequence $A$ is not all zeros.

Translated by ChatGPT 5