P4549 【Template】Bézout's Identity

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.

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

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

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