Sequence and Swaps
Contest: Educational Codeforces Round 99 (Rated for Div. 2)
Difficulty rating: 1600
Tags: dp, greedy, sortings

You are given a sequence $$$a$$$ consisting of $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, and an integer $$$x$$$. Your task is to make the sequence $$$a$$$ sorted (it is considered sorted if the condition $$$a_1 \le a_2 \le a_3 \le \dots \le a_n$$$ holds).

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$$$.

For example, if $$$a = [0, 2, 3, 5, 4]$$$, $$$x = 1$$$, the following sequence of operations is possible:

1. choose $$$i = 2$$$ (it is possible since $$$a_2 > x$$$), then $$$a = [0, 1, 3, 5, 4]$$$, $$$x = 2$$$;
2. choose $$$i = 3$$$ (it is possible since $$$a_3 > x$$$), then $$$a = [0, 1, 2, 5, 4]$$$, $$$x = 3$$$;
3. choose $$$i = 4$$$ (it is possible since $$$a_4 > x$$$), then $$$a = [0, 1, 2, 3, 4]$$$, $$$x = 5$$$.

Calculate the minimum number of operations you have to perform so that $$$a$$$ becomes sorted, or report that it is impossible.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases.

Each test case consists of two lines. 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$$$.

The second line contains $$$n$$$ integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ ($$$0 \le a_i \le 500$$$).

The sum of values of $$$n$$$ over all test cases in the input does not exceed $$$500$$$.

Output format:
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.

Constraints:
Time limit: 1.5 s
Memory limit: 512.0 MB

Example input:
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

Example output:
3
0
0
-1
1
3

Editorial:
The main fact that allows us to solve this problem is that the value of $$$x$$$ always increases after swaps, and since the resulting sequence should be sorted, the indices of elements we swap with $$$x$$$ also increase.
This observation is actually enough for us to implement a dynamic programming solution of the form "dp_{i, j} is the minimum number of actions we have to perform to reach the following situation: the last integer we swapped with $$$x$$$ was $$$a_i$$$, and the current value of $$$a_i$$$ is $$$j$$$". Depending on your implementation, it works either in $$$O(n^3)$$$ or in $$$O(n^2)$$$.
But there exists a much simpler to code greedy solution: scan the array from left to right until it is sorted, and find the first element such that we can apply the operation to it (and apply that operation to it). Implementing it in $$$O(n^2)$$$ or even in $$$O(n)$$$ is easy, but proving it is a bit harder. The key fact that is required to prove it is that if we can apply an operation to some position, but don't do it and instead apply this operation to some position to the right of that one, the elements on these two positions are no longer sorted (if we can apply the operation to some position $$$i$$$, then $$$a_i > x$$$, but if we apply the operation to position $$$j$$$ instead, then after it $$$a_i > a_j$$$). Since we can't go backward, the resulting array cannot be sorted by any means — that's why we can't skip elements in this greedy solution.