In this explanation, the “sum of abs” refers to the following formula:

\[\sum_{j=1}^{L - 1}\sum_{k = j + 1} ^ {L} |B_{j} - B_{k}|\]

When \(B\) exists, one \(B\) that minimizes \(\max(B)\) satisfies the following two conditions:

• \(B\) is sorted in ascending order.
• \(B_{1} = 0\).

The first condition holds because the sum of abs does not depend on the order of \(B\). The second condition holds because if all elements of \(B\) are positive, subtracting \(1\) from all elements can reduce \(\max(B)\) without changing the sum of abs.

When \(B\) is sorted in ascending order, the sum of abs can be expressed as follows:

\[\sum_{j = 1}^{L - 1}\sum_{k = j + 1} ^ {L} |B_{j} - B_{k}| = \sum_{j = 1}^{L - 1}\sum_{k = j + 1} ^ {L} (B_{k} - B_{j}) =\sum_{k = 1} ^ {L - 1} k(L - k)(B_{k + 1} - B_{k})\]

This transformation is correct because \(B_{a}-B_{b}=(B_{a}-B_{a-1}) + (B_{a-1}+B_{a-2}) + \cdots +(B_{b+1}-B_{b})\) for integers \(a, b\) satisfying \(1\leq b<a\leq L\), and the number of pairs \((a, b)\) satisfying \(b\leq k\) and \(k+1\leq a\) is \(k(L-k)\).

If we let \(C_{k} = B_{k + 1} - B_{k}\), then when \(B\) is sorted in ascending order and \(B_{1} = 0\), the following holds:

• \(0 \leq C_{k}\).
• The sum of abs is equal to \(\displaystyle \sum_{k = 1} ^ {L - 1} k(L - k)C_{k}\).
• \(\displaystyle\max(B) = B_{L} = \sum_{k = 1} ^ {L - 1} C_{k}\).

Therefore, we need to solve the following problem:

Determine if there exists a sequence of non-negative integers \(C\) of length \(L - 1\) such that \(\displaystyle \sum_{k = 1} ^ {L - 1} k(L - k)C_{k} = A_{i}\), and if it exists, find the minimum sum of such \(C\).

This can be solved using dynamic programming in the same manner as the knapsack problem, and it can be computed simultaneously for all \(i\).

Since \(C_{k} = 0\) always holds for \(k\) satisfying \(\max(A)<k(L-k)\), our solution has a space complexity of \(O(\max(A))\) and a time complexity of \(O(N + \max(A)\sqrt{\max(A)})\).

C++ implementation example

Python implementation example

# input
N, L = map(int, input().split())
A = list(map(int, input().split()))

# init
M = 2 * 10 ** 5
INF = 10 ** 9
dp = [INF] * (M + 1)
dp[0] = 0
k = 1

# dp
while k * (L - k) <= M and k * 2 <= L:
    # upd
    w = k * (L - k)
    for i in range(w, M + 1):
        dp[i] = min(dp[i], dp[i - w] + 1)
    # inc
    k += 1

# output
for a in A:
    print(-1 if dp[a] == INF else dp[a])