2144B.md (2069B)
1 Source: https://codeforces.com/problemset/problem/2144/B 2 3 B. Maximum Cost Permutation 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Recall that a permutation of length $n$ is a sequence of length $n$ such that each integer from $1$ to $n$ appears in it exactly once. 22 23 Let's define the cost of a permutation as the minimum length of its contiguous subsegment (possibly empty) that needs to be sorted so that the entire permutation becomes sorted in ascending order. 24 25 You are given an integer array $p$ consisting of integers from $0$ to $n$, where no positive (strictly greater than zero) integer appears more than once. You should replace zeros with integers so that the array $p$ becomes a permutation. 26 27 Your task is to calculate the maximum possible cost of the resulting permutation. 28 29 Input 30 31 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$). 34 35 The second line contains $n$ integers $p_1, p_2, \dots, p_n$ ($0 \le p_i \le n$). No positive integer appears more than once in this sequence. 36 37 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 38 39 Output 40 41 For each test case, print a single integer — the maximum possible cost of the resulting permutation. 42 43 Example 44 45 Input 46 47 ``` 48 4 49 50 5 51 52 1 0 4 0 5 53 54 3 55 56 0 0 0 57 58 4 59 60 1 2 3 0 61 62 3 63 64 0 3 2 65 ``` 66 67 Output 68 69 ``` 70 3 71 72 3 73 74 0 75 76 2 77 ``` 78 79 Note 80 81 In the first example, you can make a permutation $[1, 3, 4, 2, 5]$ with the cost $3$, because you have to sort segment $[2, 4]$. 82 83 In the second example, you can make a permutation $[2, 3, 1]$ with the cost $3$, because you have to sort segment $[1, 3]$. 84 85 In the third example, there is only one possible permutation — $[1, 2, 3, 4]$, with the cost $0$, because the permutation is already sorted. 86 87 In the fourth example, there is only one possible permutation — $[1, 3, 2]$, with the cost $2$, because you have to sort segment $[2, 3]$.