P9936 [NFLSPC #6] Arithmetic Progression

 

*Alek Sui* has solved $a_i$ problems of difficulty $i$ on a well-known OJ called *Codeforces*. He wants to solve some more problems so that $a_i$ forms an arithmetic progression with a **non-positive common difference**, because the resulting chart looks nice. Although *Alek Sui* can solve 42 problems a day, he still wants to solve as few additional problems as possible to reach the goal. You need to find the minimum number of new problems he must solve. You may assume that there are enough problems of every difficulty on the OJ.

The first line contains an integer $T$, the number of test cases. For each test case: - The first line contains an integer $n$, the number of difficulty levels. - The second line contains $n$ integers $a_i$.

For each test case, output one integer per line, the answer.

For all testdata, $1\leq T\leq 100$, $1\leq n, \sum n\leq 10 ^ 5$, $1\leq a_i\leq 10 ^ 9$. - Subtask 1 ($30$ points): $\sum n \leq 10 ^ 3$. - Subtask 2 ($70$ points): no special constraints. Source: NFLSPC #6 L by Alex_Wei Translated by ChatGPT 5