ヒント → https://atcoder.jp/contests/arc153/editorial/5482

---

[1] 変数変換による問題の言い換え

整数列 \(x = (x_1, \ldots, x_N)\) に対して、整数列 \(y = (y_1, \ldots, y_N)\) を次の式で定めます：

\[y_i = \begin{cases}x_1 & (i = 1)\\ x_i-x_{i-1} & (i\geq 2)\end{cases}\]

このとき \(x_i = \sum_{k=1}^i y_k\) なので，\(y\) から \(x\) を復元することが可能です．したがって \(x\) を求める問題を \(y\) を求める問題に言い換えることが可能です．

\[\sum_{i=1}^N \biggl(A_i\sum_{k=1}^{i}y_k\biggr) = \sum_{1\leq k\leq i\leq N}A_iy_k = \sum_{k=1}^N\biggl(\sum_{i=k}^NA_i\biggr)y_k\]

なので，\(B_k = \sum_{i=k}^NA_i\) とすれば \(y\) に関する条件は以下のようになります．

[条件 1] \(1\leq i\leq N\) に対して \(\bigl\lvert \sum_{k=1}^i y_k\bigr\rvert \leq 10^{12}\)
[条件 2] \(2\leq i\leq N\) に対して \(y_i > 0\)
[条件 3] \(\sum_{i=1}^N B_iy_i = 0\)

\(x\) が狭義単調増加であるという条件が，項ごとに独立な条件になって，扱いやすくなっています．

[条件 2] について，\(y_1\) には何の制約もないことに注意してください．

---

[2] \(B_1\neq 0\) の場合

この場合，次のように解を構成できます：

\[ y_i = \begin{cases} |B_1| & (i\geq 2) \\ -\frac{\sum_{i=2}^N B_i|B_1|}{B_1} & (i = 1)\end{cases}\]

この \(y\) が条件を満たすことを確かめます．[条件 2]・[条件 3] については明らかです．[条件 1] については，\(|B_i|\leq N\) であることから \(i\geq 2\) に対して \(|y_i| \leq N\)，\(i=1\) に対して \(|y_i|\leq (N-1)N\)，よって \(\sum_{i=1}^N|y_i| \leq 2N^2 \leq 10^{12}\) となるのでよいです．

---

[3] \(B_1 = 0\) の場合

[3 - 1] 任意の \(i\) に対して \(B_i \geq 0\) のとき

\(|B_2 - B_1| = 1\) であることなどから，\(B_2 > 0\) です．よって [条件2] のもと

\[\sum_{i=1}^N B_iy_i = \sum_{i=2}^NB_iy_i > 0\]

となるので，解は存在しません．

[3 - 2] 任意の \(i\) に対して \(B_i \leq 0\) のとき

[3 - 1] と同様に，この場合も解は存在しません．

[3 - 3] それ以外の場合

\(|B_i - B_{i+1}| = 1\) なので，この場合には \(B_p = -1\), \(B_q = 1\) であるような \(p, q\geq 2\) が存在します．

\(X = \sum_{i=2}^N B_i\) とします．\(X \geq 0\) ならば，

\[y_i = \begin{cases}1 & (i\neq p)\\ 1 + X & (i = p)\end{cases},\]

\(X< 0\) ならば

\[y_i = \begin{cases}1 & (i\neq q)\\ 1 - X & (i = q)\end{cases}\]

とすれば，条件を満たすことが確認できます．[条件 1] については，\(|B_i|\leq N\) より \(|X| \leq N^2 - N\) であることから示すことができます．