Attraction Theory

Let $f_x$ be the number of people that finish at coordinate $x$.

Since people never swap order, a final position array is uniquely determined by the count array

$$f_1,f_2,\ldots,f_n.$$

If $f_4=3$, that just means three consecutive people stand at coordinate $4$. There is no hidden permutation choice.

Reachable Count Arrays

The key characterization is:

A count array $f$ is reachable iff:

1. the positive entries form one contiguous interval $[L,R]$;
2. every strict interior count is odd:

$$f_i \text{ is odd for every } L<i<R.$$

The endpoints $f_L$ and $f_R$ only need to be positive. Their parity can be anything.

Why this is necessary:

Adjacent people start at distance $1$. Under an attraction, an adjacent gap can decrease, but it never increases. So final adjacent gaps are only $0$ or $1$, meaning occupied coordinates cannot have holes.

Now compress people standing at the same coordinate into groups. Initially every group has size $1$. An attraction at an interior coordinate merges the groups at $x-1$, $x$, and $x+1$ into one group. That is a merge of three groups. Starting from odd groups, a triple merge keeps the size odd. Only boundary groups can be made by pair merges, so only the two endpoints can have arbitrary parity.

Why this is sufficient:

Take any desired interval and counts satisfying those conditions. Think in terms of consecutive groups of original people. The left endpoint group can be made by repeatedly attracting at the left edge, merging one more group into it each time. Same for the right endpoint. Every interior target count is odd, so that block can be reduced to one group by repeatedly merging triples inside it. After all groups are built, the whole occupied block can be shifted left or right by attracting at $1$ or $n$. So the characterization is exact.

Now the problem is pure counting. Nice. The physics has left the building.

One Fixed Interval Length

Fix the occupied interval length

$$K=R-L+1.$$

For $K=1$, all $n$ people stand at one coordinate, so every coordinate contributes $n\cdot a_i$ once.

Now assume $K\ge 2$. For one fixed interval, write its counts as

$$f_1+f_2+\cdots+f_K=n,$$

where $f_1,f_K\ge 1$, and $f_2,\ldots,f_{K-1}$ are positive odd.

Encode the endpoint parities with

$$f_1=2g_1+x,\qquad f_K=2g_K+y,$$

where $x,y\in\{1,2\}$. For every interior coordinate,

$$f_i=2g_i+1.$$

There are $K-2$ interior coordinates, so after subtracting the fixed parts we need

$$g_1+g_2+\cdots+g_K=T,$$

where

$$T=\frac{n-x-y-(K-2)}{2}.$$

If $T$ is not a nonnegative integer, this parity choice gives nothing.

Otherwise, the number of solutions is

$$A=\binom{T+K-1}{K-1}.$$

Across all solutions, the total contribution of one chosen variable $g_i$ is

$$B=\binom{T+K-1}{K}.$$

This is the standard stars-and-bars marked-unit identity.

So for this fixed $(x,y)$:

• the left endpoint contributes $2B+xA$;
• the right endpoint contributes $2B+yA$;
• each interior coordinate contributes $2B+A$.

After summing over all four choices of $(x,y)$, define:

• $edge_K$ = total coefficient for one endpoint of a length-$K$ interval;
• $mid_K$ = total coefficient for one interior coordinate of a length-$K$ interval.

For interval $[L,L+K-1]$, its contribution is

$$edge_K(a_L+a_{L+K-1})+mid_K(a_{L+1}+\cdots+a_{L+K-2}).$$

Summing All Intervals Fast

For fixed $K$, let

$$E_K=\sum_{L=1}^{n-K+1}(a_L+a_{L+K-1})$$

be the sum of all endpoints, and let

$$S_K=\sum_{L=1}^{n-K+1}(a_L+a_{L+1}+\cdots+a_{L+K-1})$$

be the sum of all length-$K$ interval sums.

Then the total for this $K$ is

$$edge_K E_K+mid_K(S_K-E_K).$$

$E_K$ is just a prefix plus a suffix:

$$E_K=(a_1+\cdots+a_{n-K+1})+(a_K+\cdots+a_n).$$

For $S_K$, use prefix sums $pref_i=a_1+\cdots+a_i$:

$$S_K=\sum_{L=1}^{n-K+1}(pref_{L+K-1}-pref_{L-1}).$$

This becomes

$$\sum_{r=K}^{n} pref_r-\sum_{r=0}^{n-K} pref_r,$$

so a prefix sum over the $pref$ array gives $S_K$ in $O(1)$.

Precompute factorials and inverse factorials for binomial coefficients. Each $K$ is handled in $O(1)$, so each test case is $O(n)$, and the total input size is $2\cdot 10^5$.