upd:表格炸了

• 您点开这道题

• 您发现如果增加个位，那么可以很快（比起增加十位乃至百位），并且在十位的数字增加 $2$ 之前就可以把 $0 \sim P-1$ 表示出来

• 您发现需要找到没有出现过的最大数字，当然会由于个位进位，所以需要找到比个位小的没有出现的最大数字

• 您想到了 $\tt map$

• 您发现可以从 $0 \sim P-1$ 枚举没有出现过的，可是由于 $P \le 10^9$ 会去世

• 您发现可以通过枚举数组来找到最大值。只需要判断 $a_i-1$ 是否出现即可：

  | | | | | $a_i-3$| $a_i-2$ | $a_i-1$ | $a_i$ | | | | | | | | | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | | | | | | 无 |$a_{i-2}$| $a_{i-1}$ | $a_i$ | | | | | | | | |

• 如图，$a_{i-2}-1$ 即为 $a_i-3$，如果 $a_i-1$ 有值，那么比 $a_i$ 小的肯定会有空出来的，如果没有空出来的，那么说明不用操作了

• 由于只能增加不能减少，所以必须把 $\le$ 个位的和 $>$ 个位的分开。

• 进位之后，个位将变成 $0$，前面视情况增加 $1$。此时，由于黑板上还会有没有进位的，所以 $\tt map$ 只需要 $1$ 个就行

• 注意到进位之后 仍然 需要考虑原来的数字，另外由于进位之后 $\ge$ 个位的都写在黑板上了，所以需要判断是否 $\ge$ 个位

• 提供 Hack 数据（仅有 $n, p$ 和 $a$ 数组）

• （附在代码注释里）

#include "bits/stdc++.h"
using namespace std;

int q;
int n, p;

int f[1919810];
int a[1919810];

map<int, int> mp;

void sol() {
    int t1 = -1, t2 = -1, ans = 0;
    scanf ("%d%d", &n, &p);
    for (int i = n; i >= 1; --i) scanf ("%d", &f[i]);
    for (int i = 1; i <= n; ++i) mp[f[i]] = 1;

    for (int i = 1; i <= n; ++i) {
        if (f[i] <= f[1]) {
            if (mp[f[i] - 1] == 0) t1 = max(t1, f[i] - 1);
            //找到没有出现的数字
        } else {
            if (mp[f[i] - 1] == 0) t2 = max(t2, f[i] - 1);
            //同理
        }
    }
    if (mp[p - 1] == 0) t2 = max(t2, p - 1);
    if (t1 != -1) {
        t1 = -1;
        ans += (p - f[1]);
        //个位需要进位
        a[1] = p;
        int m = n;
        for (int i = 2; i <= n; ++i) a[i] = f[i];
        //进位
        for (int i = 1; i <= n; ++i)
            if (a[i] >= p) {
                ++a[i + 1];
                a[i] -= p;
            }
        if (a[n + 1] == 1) ++m;
        //进位后寻找没有出现的数字
        for (int i = 1; i <= m; ++i) mp[a[i]] = 1;
        for (int i = 1; i <= m; ++i) {
            if (mp[a[i] - 1] == 0 && a[i] <= f[1]) t1 = max(t1, a[i] - 1);
        }
        for (int i = 1; i <= n; ++i) {
            if (mp[f[i] - 1] == 0 && f[i] <= f[1]) t1 = max(t1, f[i] - 1);
        }
        if (mp[f[1] - 1] == 0) t1 = max(t1, f[1] - 1);
        if (t1 != -1) ans += t1;//把个位增加至那里
        printf ("%d\n", ans);
        //多测需要清空
        for (int i = 1; i <= n; ++i) mp[f[i]] = 0;
        for (int i = 1; i <= m; ++i) mp[a[i]] = 0;
        for (int i = 1; i <= n; ++i) f[i] = 0;
        for (int i = 1; i <= m; ++i) a[i] = 0;
    } else if (t2 != -1) {
        ans += t2 - f[1];//把个位增加至 t2
        printf ("%d\n", ans);
        for (int i = 1; i <= n; ++i) mp[f[i]] = 0;
        for (int i = 1; i <= n; ++i) f[i] = 0;
    } else {
        printf ("%d\n", ans);
        for (int i = 1; i <= n; ++i) mp[f[i]] = 0;
        for (int i = 1; i <= n; ++i) f[i] = 0;
    }
}

int main() {
    scanf ("%d", &q);
    while (q--) {
        sol();
    }
}
/*
Hack 1:
3 10
1 3 0
Hack 2:
5 10
8 9 9 9 9
Hack 3:
2 5
3 2
*/