解题思路

给定长度为 $n$ 的序列 $a$ 和一个额外的数 $x$，每次只能选择一个满足 $a_i>x$ 的位置 $i$，将 $a_i$ 与 $x$ 交换。目标是使 $a$ 变为非递减序列，求最少操作次数，若无法完成则输出 -1。

动态规划建模

定义状态 $\mathrm{dp}[l][x_0]$ 表示当前已处理前缀，使得前缀末尾值为 $l$，当前 $x$ 的值为 $x_0$ 时所需的最少交换次数。为了压缩状态，注意：

• $l$ 必须是最后一次放入前缀的值（保证前缀非递减，只需与 $l$ 比较）。
• $x_0$ 是当前“背包”中的值。
• 初始状态为 $\mathrm{dp}[-1][x] = 0$，表示前缀为空，且初始 $x$ 值为给定的 $x$。

题目内容

多多现在需要你帮助解决一个难题，多多得到了一个由 $n$ 个整数 $a_1,a_2,…,a_n$ 构成的序列 $a$ 和额外的一个整数 $x$，多多的任务是排序序列 $a$ 使其变为正序列，其中只要序列 $a$ 满足 $a_1 \leq a_2\leq … \leq a_n$ 就认为是一个正序列。

为了让序列 $a$ 变成正序列，多多被允许可以重复多次做这样一个操作：选择序列 $a$ 中的一个整数 $a_i(1 \leq i\leq n)$ 且满足 $a_i>x$，然后交换 $a_i$ 和 $x$。

例如对于序列 $a=[0,2,3,5,4]$ 和 $x=1$，可以通过 $3$ 次上述操作使得序列 $a$ 变成一个正序列。

$1.$选择 $i= 2$ (满足 $a_2>x$)，交换后状态为 $a=[0,1,3,5,4],x=2$;

$2.$选择 $i=3$ (满足 $a_3>x$)，交换后状态为 $a=[0,1,2,5,4],x=3$;

$3.$选择 $i=4$ (满足 $a_4>x$)，交换后状态为 $a=[0,1,2,3,4],x=5$。

多多现在需要你帮助计算出对于一个序列 $a$ 最少需要多少次上述操作能够使得其变成正序列。

输入描述

第一行包含一个整数 $t(1\leq t\leq 500)$，表示有 $t$ 组测试数据。

每组测试数据包含两行。第一行包含两个数字 $n$ 和 $x(1\leq n\leq 500,1\leq x\leq 500)$，$n$ 表示序列的长度。

接下来第二行包含 $n$ 个整数 $a_1, a_ 2,…, a_n$，其中对于仼意 $1\leq i\leq n$ 都有 $0\leq a_i\leq 500$。

输出描述

对于每组测试数据输出一个整数，代表将原序列变为正序列所需要的最小操作次数，如果无法将原序列变为正序列则输出 $-1$。

示例1

输入

6
4 1
2 3 5 4
5 6
1 1 3 4 4
1 10
2
2 10
11 9
2 10
12 11
5 18
81 324 218 413 324

输出

3
0
0
-1
1
3