1455D.md (1909B)
1 Source: https://codeforces.com/problemset/problem/1455/D 2 3 D. Sequence and Swaps 4 5 time limit per test 6 7 1.5 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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). 22 23 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 \gt x$, and swap the values of $a_i$ and $x$. 24 25 For example, if $a = [0, 2, 3, 5, 4]$, $x = 1$, the following sequence of operations is possible: 26 27 1. choose $i = 2$ (it is possible since $a_2 \gt x$), then $a = [0, 1, 3, 5, 4]$, $x = 2$; 28 2. choose $i = 3$ (it is possible since $a_3 \gt x$), then $a = [0, 1, 2, 5, 4]$, $x = 3$; 29 3. choose $i = 4$ (it is possible since $a_4 \gt x$), then $a = [0, 1, 2, 3, 4]$, $x = 5$. 30 31 Calculate the minimum number of operations you have to perform so that $a$ becomes sorted, or report that it is impossible. 32 33 Input 34 35 The first line contains one integer $t$ ($1 \le t \le 500$) — the number of test cases. 36 37 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$. 38 39 The second line contains $n$ integers $a_1$, $a_2$, ..., $a_n$ ($0 \le a_i \le 500$). 40 41 The sum of values of $n$ over all test cases in the input does not exceed $500$. 42 43 Output 44 45 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. 46 47 Example 48 49 Input 50 51 ``` 52 6 53 4 1 54 2 3 5 4 55 5 6 56 1 1 3 4 4 57 1 10 58 2 59 2 10 60 11 9 61 2 10 62 12 11 63 5 18 64 81 324 218 413 324 65 ``` 66 67 Output 68 69 ``` 70 3 71 0 72 0 73 -1 74 1 75 3 76 ```