← 返回题目列表

Codeforces · 1455/D

D. 顺序和交换

中文机器翻译题面 查看原题

给定一个序列 $$$a$$$,由 $$$n$$$ 整数 $$$a_1、a_2、\dots、a_n$$$ 和整数 $$$x$$$ 组成。您的任务是对序列 $$$a$$$ 进行排序(如果条件 $$$a_1 \le a_2 \le a_3 \le \dots \le a_n$$$ 成立,则认为已排序)。

To make the sequence sorted, you may perform the following operation any number of times you want (possibly zero): choose an integer $$$i$$$ such that $$$1 \le i \le n$$$ and $$$a_i > x$$$, and swap the values of $$$a_i$$$ and $$$x$$$.

例如,如果 $$$a = [0, 2, 3, 5, 4]$$$, $$$x = 1$$$,则可以执行以下操作序列:

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 \le t \le 500$$$) — 测试用例的数量。

每个测试用例由两行组成。 The first line contains two integers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 500$$$, $$$0 \le x \le 500$$$) — the number of elements in the sequence and the initial value of $$$x$$$.

第二行包含 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 500$$$)。

输入中所有测试用例的 $$$n$$$ 值总和不超过 $$$500$$$。

输出

For each test case, print one integer — the minimum number of operations you have to perform to make $$$a$$$ sorted, or $$$-1$$$, if it is impossible.

示例

输入 #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

输出 #1

3
0
0
-1
1
3