{"problem":{"name":"[ICPC 2021 Macao R] Cyclic Buffer","description":{"content":"There is a cyclic buffer of size $n$ with readers from the $1$-st position to the $k$-th position (both inclusive). Let $a_i$ ($1 \\le i \\le n$) be the integer at the $i$-th position of the buffer init","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9662"},"statements":[{"statement_type":"Markdown","content":"There is a cyclic buffer of size $n$ with readers from the $1$-st position to the $k$-th position (both inclusive). Let $a_i$ ($1 \\le i \\le n$) be the integer at the $i$-th position of the buffer initially. What's more, $a_1, a_2, \\cdots, a_n$ form a permutation of $n$.\n\nWe're going to visit all the integers from $1$ to $n$ (both inclusive) in increasing order. An integer can be visited only when it is residing in positions with readers (that is to say, when it is in the first $k$ positions). In case that an integer cannot be visited, we can shift the whole buffer in either directions any number of times.\n\n- If we shift the buffer to the left once, integers in the $i$-th position will be moved to the $(i - 1)$-th position if $i > 1$, and integer in the $1$-st position will be moved to the $n$-th position.\n- If we shift the buffer to the right once, integers in the $i$-th position will be moved to the $(i + 1)$-th position if $i < n$, and integer in the $n$-th position will be moved to the $1$-st position.\n\nWhat's the minimum number of times to shift the buffer so that we can visit all the integers in increasing order?\n\n## Input\n\nThere are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:\n\nThe first line contains two integers $n$ and $k$ ($1 \\le k \\le n \\le 10^6$) indicating the size of the buffer and the number of readers.\n\nThe second line contains $n$ integers $a_1, a_2, \\cdots, a_n$ ($1 \\le a_i \\le n$) where $a_i$ indicates the integer in the $i$-th position of the buffer initially.\n\nIt's guaranteed that the given $n$ integers form a permutation of $n$. It's also guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.\n\n## Output\n\nFor each test case output one line containing one integer indicating the minimum number of times to shift the buffer so that all integers can be visited in increasing order.\n\n[samples]\n\n## Note\n\nFor the first sample test case:\n- Shift to the right once so the buffer becomes $\\{1, 2, 4, 3, 5\\}$. $1$ and $2$ can now be visited in order as they are in the first $3$ positions.\n- Shift to the left twice so the buffer becomes $\\{4, 3, 5, 1, 2\\}$. $3$, $4$ and $5$ can now be visited in order as they are in the first $3$ positions.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9662","tags":["动态规划 DP","2021","O2优化","ICPC","澳门"],"sample_group":[["2\n5 3\n2 4 3 5 1\n1 1\n1","3\n0"]],"created_at":"2026-03-03 11:09:25"}}