[Solution] Wonderful Permutation Codeforces Solution

A. Wonderful Permutation

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a permutation 

𝑝1,𝑝2,…,𝑝𝑛$p_1,p_2,\dots ,p_n$ of length 𝑛$n$ and a positive integer 𝑘≤𝑛$k\le n$.

In one operation you can choose two indices 𝑖$i$ and 𝑗$j$ (1≤𝑖<𝑗≤𝑛$1\le i<j\le n$) and swap 𝑝𝑖$p_i$ with 𝑝𝑗$p_j$.

Find the minimum number of operations needed to make the sum 𝑝1+𝑝2+…+𝑝𝑘$p_1+p_2+\dots +p_k$ as small as possible.

A permutation is an array consisting of 𝑛$n$ distinct integers from 1$1$ to 𝑛$n$ in arbitrary order. For example, [2,3,1,5,4]$[2,3,1,5,4]$ is a permutation, but [1,2,2]$[1,2,2]$ is not a permutation (2$2$ appears twice in the array) and [1,3,4]$[1,3,4]$ is also not a permutation (𝑛=3$n=3$ but there is 4$4$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡$t$ (1≤𝑡≤100$1\le t\le 100$).

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 Description of the test cases follows.

The first line of each test case contains two integers 𝑛$n$ and 𝑘$k$ (1≤𝑘≤𝑛≤100$1\le k\le n\le 100$).

The second line of each test case contains 𝑛$n$ integers 𝑝1,𝑝2,…,𝑝𝑛$p_1,p_2,\dots ,p_n$ (1≤𝑝𝑖≤𝑛$1\le p_i\le n$). It is guaranteed that the given numbers form a permutation of length 𝑛$n$.

Output

For each test case print one integer — the minimum number of operations needed to make the sum 𝑝1+𝑝2+…+𝑝𝑘$p_1+p_2+\dots +p_k$ as small as possible.