Absolute Cinema

Research checked: the official Codeforces Round 1080 editorial/code at https://codeforces.com/blog/entry/151174, the problem statement at https://codeforces.com/contest/2195/problem/D, and a matching reputable video explanation at https://www.youtube.com/watch?v=eUSOiul0UmA all point to the same intended idea: use discrete second differences, then recover the two endpoints from boundary equations.

We are given

$$f(x)=\sum_{i=1}^{n} a_i |i-x|.$$

The trap is thinking we need to solve a whole linear system. We technically could, but that would be bringing a forklift to move a chair. The function $|i-x|$ has a kink exactly at $x=i$, and that kink is the whole problem.

Consider the second difference

$$\Delta^2 f(x)=f(x+1)-2f(x)+f(x-1)$$

for an interior position $2 \le x \le n-1$.

For a fixed index $i$, look at

$$|i-(x+1)|-2|i-x|+|i-(x-1)|.$$

If $i \ne x$, then around $x$ the function is linear or the values still cancel out. In all such cases, this expression is $0$.

If $i=x$, then it becomes

$$|x-(x+1)|-2|x-x|+|x-(x-1)|=1-0+1=2.$$

Therefore all terms vanish except the one with $i=x$, giving

$$f(x+1)-2f(x)+f(x-1)=2a_x.$$

So for every interior index,

$$a_x=\frac{f(x+1)-2f(x)+f(x-1)}{2}.$$

This recovers $a_2,a_3,\dots,a_{n-1}$ in linear time.

Now we only need $a_1$ and $a_n$.

Use $f(n)$:

$$f(n)=\sum_{i=1}^{n} a_i |i-n|=\sum_{i=1}^{n-1} a_i(n-i).$$

The term for $a_n$ is zero, so after subtracting the known interior contribution, the remainder is

$$a_1(n-1).$$

Thus

$$a_1=\frac{f(n)-\sum_{i=2}^{n-1} a_i(n-i)}{n-1}.$$

Similarly, use $f(1)$:

$$f(1)=\sum_{i=2}^{n} a_i(i-1).$$

The term for $a_1$ is zero. After subtracting the known interior contribution, the remainder is

$$a_n(n-1),$$

so

$$a_n=\frac{f(1)-\sum_{i=2}^{n-1} a_i(i-1)}{n-1}.$$

The case $n=2$ also works automatically: there are no interior values, so $a_1=f(2)$ and $a_2=f(1)$.

All arithmetic must use long long, because $f(i)$ can be as large as $10^{14}$. The final answers fit in $[-1000,1000]$, but intermediate values do not care about your feelings.

Complexity:

$$O(n)$$

per test case, and

$$O\left(\sum n\right)$$

over all tests. Memory usage is $O(n)$ for the input/output arrays.